Cycle Sort

Cycle sort is an in-place sorting Algorithm, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array.

• It is optimal in terms of number of memory writes. It minimizes the number of memory writes to sort (Each value is either written zero times, if it’s already in its correct position, or written one time to its correct position.)
• It is based on the idea that array to be sorted can be divided into cycles. Cycles can be visualized as a graph. We have n nodes and an edge directed from node i to node j if the element at i-th index must be present at j-th index in the sorted array.

We one by one consider all cycles. We first consider the cycle that includes first element. We find correct position of first element, place it at its correct position, say j. We consider old value of arr[j] and find its correct position, we keep doing this till all elements of current cycle are placed at correct position, i.e., we don’t come back to cycle starting point.

EXPLANATION:

arr[] = {10, 5, 2, 3}
 index =  0   1   2   3
cycle_start = 0 
item = 10 = arr[0]

Find position where we put the item  
pos = cycle_start
while (arr[i] < item)  
    pos++;

We put 10 at arr[3] and change item to 
old value of arr[3].
arr[] = {10, 5, 2, 10} 
item = 3 

Again rotate rest cycle that start with index '0' 
Find position where we put the item = 3 
we swap item with element at arr[1] now 
arr[] = {10, 3, 2, 10} 
item = 5

Again rotate rest cycle that start with index '0' and item = 5 
we swap item with element at arr[2].
arr[] = {10, 3, 5, 10 } 
item = 2

Again rotate rest cycle that start with index '0' and item = 2
arr[] = {2, 3,  5, 10}  

Above is one iteration for cycle_stat = 0.
Repeat above steps for cycle_start = 1, 2, ..n-2

CODE:

# Python program to implement cycle sort 
  
def cycleSort(array): 
  writes = 0
    
  # 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] 
    writes += 1
      
    # 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] 
      writes += 1
    
  return writes 
    
# driver code  
arr = [1, 8, 3, 9, 10, 10, 2, 4 ] 
n = len(arr)  
cycleSort(arr) 
  
print("After sort : ") 
for i in range(0, n) :  
    print(arr[i], end = ' ') 

Output:           After sort :
1 2 3 4 8 9 10 10

Time Complexity : O(n²)
Worst Case : O(n²)
Average Case: O(n²)
Best Case : O(n²)

This sorting algorithm is best suited for situations where memory write or swap operations are costly.