Cycle sort

Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array. It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result. Unlike nearly every other sort, items are never written elsewhere in the array simply to push them out of the way of the action. Each value is either written zero times, if it is 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. Minimizing the number of writes is useful when making writes to some huge data set is very expensive, such as with EEPROMs like Flash memory where each write reduces the lifespan of the memory.

Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array. It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result. Unlike nearly every other sort, items are never written elsewhere in the array simply to push them out of the way of the action. Each value is either written zero times, if it is 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. Minimizing the number of writes is useful when making writes to some huge data set is very expensive, such as with EEPROMs like Flash memory where each write reduces the lifespan of the memory. def cycle_sort(array) -> int: """Sort an array in place and return the number of writes.""" writes = 0 # Loop through the array to find cycles to rotate. # Note that the last item will already be sorted after the first n-1 cycles. for cycle_start in range(0, len(array) - 1): item = array[cycle_start] # Find where to put the item. pos = cycle_start for i in range(cycle_start + 1, len(array)): if array[i] The next implementation written in C++ simply performs cyclic array sorting. template void cycle_sort(type_array *Array, int array_size) { for (int cycle_start = 0; cycle_start ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1372636393 under CC BY-SA 4.0; modifications have been made.