Cycle Sort - Python

Cycle Sort is an in-place sorting algorithm that minimizes the number of write operations by placing each element directly into its correct position. It is mainly used when write operations are costly, such as in memory-constrained systems.

Cycle in arr[] = {2, 4, 5, 1, 3}:

Algorithm Steps

1. Start from the first element and determine its correct position in the sorted array.
2. Place the element in its correct position. If this displaces another element, continue rotating the displaced elements until the cycle is complete.
3. Repeat for the next element not yet in its correct position.
4. Continue until the entire array is sorted.

Dry Run of the Cycle Sort

Initial Array: [4, 3, 1, 2]

Cycle Start 0: item = 4

• Find correct position of 4 -> pos = 3
• Swap 4 with arr[3] (2) -> [2, 3, 1, 4], item = 2
• Find correct position of 2 -> pos = 1
• Swap 2 with arr[1] (3) -> [3, 2, 1, 4], item = 3
• Find correct position of 3 -> pos = 2
• Swap 3 with arr[2] (1) -> [1, 2, 3, 4], item = 1
• Find correct position of 1 -> pos = 0 (already in place, cycle ends)

Array after Cycle 0: [1, 2, 3, 4]

Cycle Start 1: item = 2 -> already in correct position, skip
Cycle Start 2: item = 3 -> already in correct position, skip
Cycle Start 3: item = 4 -> already in correct position, skip

Sorted Array: [1, 2, 3, 4]

Python Implementation

arr = [4,3,1,2]
writes = 0
n = len(arr)

for cycleStart in range(0, n - 1):
    item = arr[cycleStart]

    pos = cycleStart
    for i in range(cycleStart + 1, n):
        if arr[i] < item:
            pos += 1

    if pos == cycleStart:
        continue
    
    while item == arr[pos]:
        pos += 1
    arr[pos], item = item, arr[pos]
    writes += 1

    while pos != cycleStart:
        
        pos = cycleStart
        for i in range(cycleStart + 1, n):
            if arr[i] < item:
                pos += 1

        while item == arr[pos]:
            pos += 1
        arr[pos], item = item, arr[pos]
        writes += 1

print("After sort : ")
for i in range(n):
    print(arr[i], end=' ')

After sort : 
1 2 3 4 

Explanation:

• for cycleStart in range(0, n - 1): Loop through the array to find cycles.
• item = arr[cycleStart] -> Pick the item to place in its correct position.
• pos = cycleStart; for i in range(cycleStart + 1, n): if arr[i] < item: pos += 1 -> Count elements smaller than item to find its correct position.
• if pos == cycleStart: continue -> Skip if the item is already in the correct position.
• while item == arr[pos]: pos += 1 -> Skip duplicates.
• arr[pos], item = item, arr[pos]; writes += 1 -> Place the item and increment writes.
• while pos != cycleStart: Rotate remaining items in the cycle.
• Same steps are repeated to place each element in its cycle.

Related Articles:

• QuickSort - Python
• Bubble Sort - Python