Cycle Sort Implementation in Python

Cycle sort is an in-place, unstable sorting algorithm that is known for its efficiency in minimizing the number of writes. The algorithm is based on the idea that the permutation to be sorted can be factored into cycles, and then each cycle can be rotated to place the minimum element in the correct position.

How Cycle Sort Works

The algorithm works by following these steps:

1. Iterate through the input array
2. For each element in the array, find the correct position in the sorted sequence
3. Rotate the cycle to bring the minimum element to the correct position

Cycle Sort Implementation

Here’s the implementation of Cycle Sort in Python:

def cycle_sort(array):
    # Loop through the array to find cycles to rotate
    for cycleStart in range(0, len(array) - 1):
        item = array[cycleStart]
        
        # Find where to put the item
        pos = cycleStart
        for i in range(cycleStart + 1, len(array)):
            if array[i] < item:
                pos += 1
        
        # If the item is already there, this is not a cycle
        if pos == cycleStart:
            continue
        
        # Otherwise, put the item there or right after any duplicates
        while item == array[pos]:
            pos += 1
        array[pos], item = item, array[pos]
        
        # Rotate the rest of the cycle
        while pos != cycleStart:
            # Find where to put the item
            pos = cycleStart
            for i in range(cycleStart + 1, len(array)):
                if array[i] < item:
                    pos += 1
        
            # Put the item there or right after any duplicates
            while item == array[pos]:
                pos += 1
            array[pos], item = item, array[pos]
    
    return array

Let’s break down the implementation and understand each step:

Step 1 – Loop through the array to find cycles to rotate

The first step is to loop through the array to find cycles to rotate:

for cycleStart in range(0, len(array) - 1):
    item = array[cycleStart]

We initialize a variable cycleStart to 0 and iterate until the second last element in the array. For each iteration, we store the element at cycleStart in a variable called item.

Step 2 – Find where to put the item

The next step is to find the correct position of the item in the sorted sequence:

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

We initialize a variable pos to cycleStart and iterate from cycleStart + 1 to the end of the array. For each iteration, we compare the current element with the item. If the current element is less than the item, we increment the pos.

Step 3 – Put the item in the correct position

The next step is to put the item in the correct position:

# If the item is already there, this is not a cycle
if pos == cycleStart:
    continue

# Otherwise, put the item there or right after any duplicates
while item == array[pos]:
    pos += 1
array[pos], item = item, array[pos]

If the item is already in the correct position, we move on to the next iteration. Otherwise, we put the item in the correct position or right after any duplicates. We use a while loop to check if there are any duplicates of the item at the pos, and if so, we move the pos to the next index. Once we have found the correct position, we swap the item with the element at the pos.

Step 4 – Rotate the rest of the cycle

The final step is to rotate the rest of the cycle:

while pos != cycleStart:
    # Find where to put the item
    pos = cycleStart
    for i in range(cycleStart + 1, len(array)):
        if array[i] < item:
            pos += 1
    # Put the item there or right after any duplicates
    while item == array[pos]:
        pos += 1
    array[pos], item = item, array[pos]

We use a while loop to continue rotating the cycle until we have reached the cycleStart. We repeat the same process as before to find the correct position and put the item in the correct place. This step ensures that all the elements in the cycle are in their correct positions.

Step 5 – Return the sorted array

Finally, we return the sorted array:

return array

This completes the implementation of the Cycle Sort algorithm.

Cycle Sort Time Complexity

The time complexity of Cycle Sort is O(n^2), which is the same as that of Selection Sort and Insertion Sort. However, the number of writes or swaps is less than both Selection Sort and Insertion Sort, making it more efficient in terms of minimizing the number of writes. The space complexity of Cycle Sort is O(1), as the algorithm sorts the input array in place.

Cycle Sort Advantages and Disadvantages

Advantages:

• Efficient in minimizing the number of writes or swaps
• In-place sorting algorithm
• Stable sorting algorithm

Disadvantages:

• The time complexity of O(n^2) makes it inefficient for large arrays
• Not a widely used sorting algorithm

When to use Cycle Sort

Cycle Sort can be used when the number of writes or swaps needs to be minimized, and the input array is small or has mostly sorted elements. It is not recommended for large arrays or when time complexity is a critical factor.

Conclusion

Cycle Sort is an efficient sorting algorithm that minimizes the number of writes or swaps. It is based on the idea of finding cycles in the permutation to be sorted and rotating each cycle to place the minimum element in the correct position. Although its time complexity is O(n^2), it is still useful in some cases where minimizing writes or swaps is more important than time complexity.