Class: | Sorting algorithm |
Data: | Array |
Time: | Θ(n2) |
Best-Time: | Θ(n2) |
Average-Time: | Θ(n2) |
Space: | Θ(n) total, Θ(1) auxiliary |
Optimal: | No |
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, unlike any other in-place sorting algorithm. 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'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.
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.
To illustrate the idea of cycle sort, consider a list with distinct elements. Given an element
x
x
y
x
Repeating this process for every element sorts the list, with a single writing operation if and only if an element is not already at its correct position. While computing the correct positions takes
O(n)
To create a working implementation from the above outline, two issues need to be addressed:
x
x
The following Python implementation[1] performs cycle sort on an array, counting the number of writes to that array that were needed to sort it.
Python
# 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] < item: pos += 1
# If the item is already there, this is not a cycle. if pos
# Otherwise, put the item there or right after any duplicates. while item
array[pos], item = item, array[pos] writes += 1
# Rotate the rest of the cycle. while pos != cycle_start: # Find where to put the item. pos = cycle_start for i in range(cycle_start + 1, len(array)): if array[i] < item: pos += 1
# Put the item there or right after any duplicates. while item
return writes
The next implementation written in C++ simply performs cyclic array sorting.
When the array contains only duplicates of a relatively small number of items, a constant-time perfect hash function can greatly speed up finding where to put an item, turning the sort from Θ(n2) time to Θ(n + k) time, where k is the total number of hashes. The array ends up sorted in the order of the hashes, so choosing a hash function that gives you the right ordering is important.
Before the sort, create a histogram, sorted by hash, counting the number of occurrences of each hash in the array. Then create a table with the cumulative sum of each entry in the histogram. The cumulative sum table will then contain the position in the array of each element. The proper place of elements can then be found by a constant-time hashing and cumulative sum table lookup rather than a linear search.
"Cycle-Sort: A Linear Sorting Method", The Computer Journal (1990) 33 (4): 365-367.