# 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:

**Find the Correct Position**: For each element, find the correct position by counting the number of elements that are smaller.**Place the Element**: If the element is not already at the correct position, place it there. If it is a duplicate, skip it.**Rotate the Cycle**: Rotate the rest of the cycle to place all elements in their correct positions.**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.