Python Program for Cycle Sort

Cycle sort is a comparison sort that is potentially the most efficient in terms of total writes to the original array. In this tutorial, we are going to sort an array with help of the cycle sort method.

Cycle Sort - A basic Introduction

Cycle sort is the most efficient in terms of memory writes. It reduces the amount of memory writes required to sort. If a value is already in the proper location, it is written zero times; otherwise, it is written one to the correct spot.

• It is based on the concept of dividing a sortable array into cycles. A graph can be used to represent a cycle.
• All of the cycles are considered one by one. First, we'll look at the cycle that contains the first element. We determine the right position of the first element and set it there, say j. We take the old value of arr[j] and locate its right location; we repeat this process until all components of the current cycle are correctly positioned, i.e., we do not return to the cycle's beginning point.

Let us look at the diagram below for a better understanding:

Algorithm

As of now, we have a rough understanding of the Gnome sort operation. Let's have a look at the Algorithm followed by code for better understanding:

1. Create a function cycle_sort()
2. Pass array as a parameter
3. Loop through the array to find cycles to rotate
4. Find the location to put the items
5. If the item is there, no cycle found
6. Place the item there or immediately after any duplicates.
7. Rotate the rest of the cycle
8. Follow steps 5-6 until the array is sorted.
9. Print the sorted array

Program for Cycle Sort

The source code for a Python program that implements Gnome sort is given below. The output of the program is displayed below. The program is solely influenced by the algorithm:

def cycle_Sort(array):
  write = 0
   
  for cycle in range(0, len(array) - 1):
    ele = array[cycle]
     
    position = cycle
    for i in range(cycle + 1, len(array)):
      if array[i] < ele:
        position += 1
     
    if position == cycle:
      continue
     
    while ele == array[position]:
      position += 1
    array[position], ele = ele, array[position]
    write += 1
     
    while position != cycle:
       
      position = cycle
      for a in range(cycle + 1, len(array)):
        if array[a] < ele:
          position += 1
       
      while ele == array[position]:
        position += 1
      array[position], ele = ele, array[position]
      write += 1
   
  return write
   
# driver code
array = [2, 4, 5, 1, 3]
print("The original array is:", array)
n = len(array)
cycle_Sort(array)
print("The sorted array is: ",array)

The original array is: [2, 4, 5, 1, 3]
The sorted array is: [1, 2, 3, 4, 5]

Conclusion

In this tutorial, we have performed a cycle sort operation in python to sort an array. It is an unstable program having the time complexity of O(n²) and the space complexity of the cycle sort is O(1).