Cycle sort algorithm

In this article, we will discuss the Cycle sort Algorithm. Cycle sort is a comparison sorting algorithm that forces array to be factored into the number of cycles where each of them can be rotated to produce a sorted array. It is theoretically optimal in the sense that it reduces the number of writes to the original array.

It is an in-place and unstable sorting algorithm. Cycle sort forces an array to be factored into a number of cycles where every element can rotate in order to produce a sorted array. The time complexity of cycle sort is O(n²), even in the best case.

Now, let’s see the algorithm of cycle sort.

Algorithm

Suppose there is an array arr with n distinct elements. Given an element A, we can find its index by counting the number of elements smaller than A.

If the element is at its correct position, simply leave it as it is.
Else, we have to find the correct position of A by counting the number of elements smaller than it. Another element B is replaced to be moved to its correct position. This process continues until we get an element at the original position of A.

The above-illustrated process constitutes a cycle. Repeat this cycle for every element of the list until the list is sorted.

Working of Cycle sort Algorithm

Now, let’s see the working of Cycle sort Algorithm. To understand the working of cycle sort algorithm, let’s take an unsorted array.

Let the elements of array are – {30, 20, 10, 40, 60, 50}

Cycle Sort

Now, the given array is completely sorted.

Cycle sort complexity

Now, let’s see the time complexity of cycle sort in the best case, average case, and worst case. We will also see the space complexity of cycle sort.

1. Time Complexity

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

The time complexity of cycle sort in all three cases in O(n²). Even in the best case, it takes O(n²) time to sort the array elements. In Cycle sort, there is always the traversing of the entire subarray from the current position in order to count the number of elements less than the current element.

So, in cycle sort, it doesn’t matter whether the given array is already sorted or not. It has no consequence on the running time of the algorithm. So, the cycle sort must run in the quadratic time.

2. Space Complexity

Space Complexity	O(1)
Stable	No

The space complexity of cycle sort is O(1).

Implementation of Cycle sort

Now, let’s see the programs of cycle sort in different programming languages.

Program: Write a program to implement cycle sort in C language.

  #include      /*function to implement to cycle sort*/  void cycleSort(int a[], int n)    {        int start, element, pos, temp, i;            /*Loop to traverse the array elements and place them on the correct position*/      for (start = 0; start <= n – 2; start++) {            element = a[start];                    /*position to place the element*/          pos = start;                      for (i = start + 1; i < n; i++)                if (a[i] < element)                    pos++;            if (pos == start)  /*if the element is at exact position*/              continue;            while (element == a[pos])                pos += 1;            if (pos != start) /*put element at its exact position*/           {                //swap(element, a[pos]);                temp = element;                element = a[pos];                a[pos] = temp;              }            /*Rotate rest of the elements*/          while (pos != start)           {                pos = start;                /*find position to put the element*/              for (i = start + 1; i < n; i++)                    if (a[i] < element)                        pos += 1;                              /*Ignore duplicate elements*/              while (element == a[pos])                    pos += 1;                              /*put element to its correct position*/              if (element != a[pos])               {                    temp = element;                    element = a[pos];                    a[pos] = temp;                  }            }        }          }         void print(int a[], int n) /*function to print array elements*/      {      int i;      for(i = 0; i < n; i++)        {            printf(“%d “,a[i]);        }            }         int main()    {        int a[] = {90, 45, 30, 20, 10, 40, 60, 50, 5, 2};        int n = sizeof(a) / sizeof(a[0]);        printf(“Before sorting array elements are – n”);      print(a, n);      cycleSort(a, n);        printf(“nAfter applying cycle sort, array elements are – n”);        print(a, n);      return 0;    }  

Output

Cycle Sort

Program: Write a program to implement cycle sort in C++.

  #include     using namespace std;    /*function to implement to cycle sort*/  void cycleSort(int a[], int n)    {        int start, element, pos, temp, i;            /*Loop to traverse the array elements and place them on the correct position*/      for (start = 0; start <= n – 2; start++) {            element = a[start];                    /*position to place the element*/          pos = start;                      for (i = start + 1; i < n; i++)                if (a[i] < element)                    pos++;            if (pos == start)  /*if the element is at exact position*/              continue;            while (element == a[pos])                pos += 1;            if (pos != start) /*put element at its exact position*/           {                //swap(element, a[pos]);                temp = element;                element = a[pos];                a[pos] = temp;                  }            /*Rotate rest of the elements*/          while (pos != start)           {                pos = start;                /*find position to put the element*/              for (i = start + 1; i < n; i++)                    if (a[i] < element)                        pos += 1;                              /*Ignore duplicate elements*/              while (element == a[pos])                    pos += 1;                              /*put element to its correct position*/              if (element != a[pos])               {                    temp = element;                    element = a[pos];                    a[pos] = temp;                  }            }        }          }         void print(int a[], int n) /*function to print array elements*/      {      int i;      for(i = 0; i < n; i++)        {            cout<<a a="" applying="" are="" array="" cout="" cycle="" cyclesort="" elements="" int="" main="" n="sizeof(a)" print="" return="" sizeof="" sort="" sorting="" textarea=""></a>[i]

Output

Cycle Sort

Program: Write a program to implement cycle sort in C#.

  using System;  class CycleSort {    /*function to implement to cycle sort*/  static void cycleSort(int[] a, int n)    {        int start, element, pos, temp, i;            /*Loop to traverse the array elements and place them on the correct position*/      for (start = 0; start <= n – 2; start++) {            element = a[start];                    /*position to place the element*/          pos = start;                      for (i = start + 1; i < n; i++)                if (a[i] < element)                    pos++;            if (pos == start)  /*if the element is at exact position*/              continue;            while (element == a[pos])                pos += 1;            if (pos != start) /*put element at its exact position*/           {                //swap(element, a[pos]);                temp = element;                element = a[pos];                a[pos] = temp;              }            /*Rotate rest of the elements*/          while (pos != start)           {                pos = start;                /*find position to put the element*/              for (i = start + 1; i < n; i++)                    if (a[i] < element)                        pos += 1;                              /*Ignore duplicate elements*/              while (element == a[pos])                    pos += 1;                              /*put element to its correct position*/              if (element != a[pos])               {                    temp = element;                    element = a[pos];                    a[pos] = temp;                  }            }        }          }         static void print(int[] a, int n) /*function to print array elements*/      {      int i;      for(i = 0; i < n; i++)        {            Console.Write(a[i] + ” “);        }            }            static void Main()      {      int[] a = {88, 43, 28, 18, 8, 38, 58, 48, 3, 0};        int n = a.Length;        Console.Write(“Before sorting array elements are – n”);      print(a, n);      cycleSort(a, n);        Console.Write(“nAfter applying cycle sort, array elements are – n”);        print(a, n);  }    }  

Output

After the execution of the above code, the output will be –

Cycle Sort

Program: Write a program to implement cycle sort in Java.

  class CycleSort   {  /*function to implement to cycle sort*/  static void cycleSort(int a[], int n)    {        int start, element, pos, temp, i;            /*Loop to traverse the array elements and place them on the correct     position*/      for (start = 0; start <= n – 2; start++) {            element = a[start];                    /*position to place the element*/          pos = start;                      for (i = start + 1; i < n; i++)                if (a[i] < element)                    pos++;            if (pos == start)  /*if the element is at exact position*/              continue;            while (element == a[pos])                pos += 1;            if (pos != start) /*put element at its exact position*/           {                //swap(element, a[pos]);                temp = element;                element = a[pos];                a[pos] = temp;              }            /*Rotate rest of the elements*/          while (pos != start)           {                pos = start;                /*find position to put the element*/              for (i = start + 1; i < n; i++)                    if (a[i] < element)                        pos += 1;                              /*Ignore duplicate elements*/              while (element == a[pos])                    pos += 1;                              /*put element to its correct position*/              if (element != a[pos])               {                    temp = element;                    element = a[pos];                    a[pos] = temp;                  }            }        }          }         static void print(int a[], int n) /*function to print array elements*/      {      int i;      for(i = 0; i < n; i++)        {            System.out.print(a[i] + ” “);        }            }         public static void main(String args[])      {      int[] a = {87, 42, 27, 17, 7, 37, 57, 47, 2, 1};        int n = a.length;        System.out.print(“Before sorting array elements are – n”);      print(a, n);      cycleSort(a, n);        System.out.print(“nAfter applying cycle sort, array elements are – n”);        print(a, n);  }    }  

Output

After the execution of the above code, the output will be –

Cycle Sort

So, that’s all about the article. Hope, the article will be helpful and informative to you.

Next TopicTim Sort

Cycle Sort

Cycle sort algorithm

Algorithm

Working of Cycle sort Algorithm

Cycle sort complexity

1. Time Complexity

2. Space Complexity

Implementation of Cycle sort

DS Array representation of Queue

DS | Array vs linked list

You may also like