Cycle sort is a comparison-based sorting algorithm that is in-place and not stable. It works by finding cycles in the permutation of the array and rotating the elements within each cycle to place them in their correct positions. Cycle sort is known for its minimal number of writes to the array, making it useful for situations where write operations are costly. The time complexity of cycle sort is O(n^2), but it minimizes the number of writes, making it efficient for memory writes.
Consider an array with the following elements:
[1, 8, 3, 9, 10, 10, 2, 4]
To sort this array using cycle sort, follow these steps:
Let's apply these steps to the example array:
Below is the pseudo code for the cycle sort algorithm:
function cycleSort(array)
n = length(array)
for cycleStart = 0 to n - 2 do
item = array[cycleStart]
pos = cycleStart
for i = cycleStart + 1 to n - 1 do
if array[i] < item then
pos += 1
end for
if pos == cycleStart then
continue
while item == array[pos] do
pos += 1
end while
if pos != cycleStart then
swap(item, array[pos])
while pos != cycleStart do
pos = cycleStart
for i = cycleStart + 1 to n - 1 do
if array[i] < item then
pos += 1
end for
while item == array[pos] do
pos += 1
end while
if item != array[pos] then
swap(item, array[pos])
end while
end for
end function
Explanation:
def cycle_sort(arr):
n = len(arr)
writes = 0
for cycle_start in range(0, n - 1):
item = arr[cycle_start]
pos = cycle_start
for i in range(cycle_start + 1, n):
if arr[i] < item:
pos += 1
if pos == cycle_start:
continue
while item == arr[pos]:
pos += 1
arr[pos], item = item, arr[pos]
writes += 1
while pos != cycle_start:
pos = cycle_start
for i in range(cycle_start + 1, n):
if arr[i] < item:
pos += 1
while item == arr[pos]:
pos += 1
arr[pos], item = item, arr[pos]
writes += 1
return arr, writes
# Example usage:
array = [1, 8, 3, 9, 10, 10, 2, 4]
print("Original array:", array)
sorted_array, writes = cycle_sort(array)
print("Sorted array:", sorted_array) # Output: [1, 2, 3, 4, 8, 9, 10, 10]
print("Number of writes:", writes)
This Python program defines a function to perform cycle sort on an array. The function iterates through the array, finds the correct position for each element, places it there, and rotates the cycle to place all elements in their correct positions, minimizing the number of write operations.