Cycle Sort Algorithm

Introduction to Cycle Sort

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.

---

Step-by-Step Process

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:

1. Find the Correct Position: For each element, find the correct position by counting the number of elements that are smaller.
2. Place the Element: If the element is not already at the correct position, place it there. If it is a duplicate, skip it.
3. Rotate the Cycle: Rotate the rest of the cycle to place all elements in their correct positions.
4. Repeat: Continue the process for each element in the array.

Let's apply these steps to the example array:

• Initial array: [1, 8, 3, 9, 10, 10, 2, 4]
• Position 1 at index 0: Already in the correct position
• Position 8 at index 1: Move to the correct position at index 6
• Position 3 at index 1: Move to the correct position at index 2
• Continue rotating the cycle for each element
• Final sorted array: [1, 2, 3, 4, 8, 9, 10, 10]

---

Pseudo Code for Cycle Sort

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:

• Initialize: The cycleSort function starts by iterating through the array from the first to the second last element.
• Find Correct Position: For each element, the correct position is found by counting the number of elements smaller than the current element.
• Place Element: If the element is not already in its correct position, it is placed there. Duplicates are handled by skipping the position.
• Rotate Cycle: The rest of the cycle is rotated to place all elements in their correct positions.
• Repeat: The process repeats for each element in the array.

---

Python Program to Implement Cycle Sort

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.