# 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
**s****mall 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**

**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**

**Output**

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

**Time complexity **in big O notation will be **n**** ^{2}**.

**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

You must be logged in to post a comment.