Which sorting algorithm makes minimum number of memory writes? | GeeksforGeeks
Among the sorting algorithms that we generally study in our data structure and algorithm courses, Selection Sort makes least number of writes (it makes O(n) swaps). But, Cycle Sort almost always makes less number of writes compared to Selection Sort. In Cycle Sort, each value is either written zero times, if it’s already in its correct position, or written one time to its correct position. This matches the minimal number of overwrites required for a completed in-place sort.
Cyclesort
Cycles
Lets start with the definition of a cycle. A cycle is a subset of elements from a permutation that have been rotated from their original position. So, say we have an ordered set [0, 1, 2, 3, 4], and a cycle [0, 3, 1]. The cycle defines a rotation where element 0 moves to position 3, 3 to 1 and 1 to 0. Visually, it looks like this:
Read full article from Which sorting algorithm makes minimum number of memory writes? | GeeksforGeeks
Among the sorting algorithms that we generally study in our data structure and algorithm courses, Selection Sort makes least number of writes (it makes O(n) swaps). But, Cycle Sort almost always makes less number of writes compared to Selection Sort. In Cycle Sort, each value is either written zero times, if it’s already in its correct position, or written one time to its correct position. This matches the minimal number of overwrites required for a completed in-place sort.
Cyclesort
Cycles
Lets start with the definition of a cycle. A cycle is a subset of elements from a permutation that have been rotated from their original position. So, say we have an ordered set [0, 1, 2, 3, 4], and a cycle [0, 3, 1]. The cycle defines a rotation where element 0 moves to position 3, 3 to 1 and 1 to 0. Visually, it looks like this:
We can apply a cycle to an ordered set to obtain a permutation, and we can then reverse that cycle to re-obtain the original set.
Read full article from Which sorting algorithm makes minimum number of memory writes? | GeeksforGeeks
