Implementation of Cycle Sort in C++

Hi, In this tutorial we are going to learn about cycle sort and its implementation in C++. Sorting is used to rearrange sequences in some specific order, i.e. either ascending or descending order. Here we will understand cycle sort and will implement it for ascending order case.
Cycle sort is a comparison sort, which divides given sequence into some cycles and then rotates them to get a sorted array. This is the theoretically optimal sorting technique.

Let’s understand the algorithm for cycle sort.

Algorithm and implementation for Cycle Sort in C++

void cycle_sort( int a[] , int n )

We will use this function in our implementation to sort a given sequence.

• Parameters for the function are, given array itself and its size.
• We will declare a pointer and will set it to the first element and will store in a small variable, how many elements in the array are smaller than him.
• Now we will swap this pointer with a[small].
• We will keep doing this until it completes a cycle, i.e. pointer returns to the first element.
• Also, we will take care of repeated numbers by increasing small variables for every matched pair at that location.
• And if the pointed element is already on its position we will increase the pointer to the next element.
• Then using for loop we will repeat this process till the second last element i.e. a[n-2].

int main()

• We will define an initial unsorted array first.
• Then we will call cycle_sort(a, n) function.
• Finally, will print the sorted array.

Look at this Visualization for better understanding.

Now, look at the implementation of this Algorithm.

Code

#include <bits/stdc++.h>
using namespace std;

// cycle sort function
void cycle_sort(int a[], int n){
    int element,small; 
    // i is the pointer and will iterate the array till i=n-2 
    for(int i=0; i<=n-2; i++){  
        element=a[i];
        // small set to i because till i every element will be
        // smaller than a[i] so we can start checking from i+1  
        small=i;  
        for(int j=i+1; j<n; j++){  
            if(a[j]<element){  
                small++;
            }
        } 
        // skip if already set 
        if(small==i){  
            continue; 
        }
        // increasing small in case of repeated numbers 
        while(element==a[small]){ 
            small++; 
        } 
        // again checking whether already set or not 
        // if not we will swap the a[small] and element
        if(small!=i){    
            //temp=element;  
            //element=a[small];  
            //a[small]=temp; 
            swap(a[small],element);     
        }  
        // iterating through till we complete the whole cycle
        while (small!=i){
            // small set to i because till i every element will be
            // smaller than a[i] so we can start checking from i+1  
            small=i;  
            for(int j=i+1; j<n; j++){ 
                if(a[j]<element){  
                    small+=1;
                }
            }
            // increasing small in case of repeated numbers  
            while(element==a[small]){  
                small+=1;
            }  
            // finally swapping if not equal
            if(element!=a[small]){  
                //temp=element;  
                //element=a[small];  
                //a[small]=temp; 
                swap(a[small],element);       
            }  
        }  
    } 
}

// driver function
int main(){
    // input array
    int a[7]={5,2,1,7,1,-1,0};
    // calling cycle sort function
    cycle_sort(a,sizeof(a)/sizeof(a[0]));
    // printitng the sorted array
    cout<<"Array after being sorted: \n";
    for(auto i:a){
        cout<<i<<" ";
    }
    cout<<endl;
    return 0;
}

Output

Array after being sorted:
-1 0 1 1 2 5 7

Time complexity in big O notation will be n².
Space complexity will be 1.

This is it for this tutorial.
Hope you will learn from it.
You can also check out my other blogs.

1. Strand Sort in C++
2. How to append a vector to a vector in C++
3. How to flatten a 2-Dimensional vector in C++

Peace.