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 n2.
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.
- Strand Sort in C++
- How to append a vector to a vector in C++
- How to flatten a 2-Dimensional vector in C++
Peace.
Leave a Reply