We know various algorithms for sorting. Here we will see a new approach, cyclic shift for sorting the array. Cyclic shift means separating out a subarray from the given array and applying cyclic shift or rotation on the subarray by any offset, and then putting it back to the same position.

//c++ implementation of sorting by cyclic shift
#include<bits/stdc++.h>
using namespace std;
//function for cyclic shift
int cyclicShiftSort(vector<int>& arr,int n)
{
int count=0; //no of cyclic shift
//creating a copy of arr
vector<int> cpy(arr.begin(),arr.end());
//sorting the copy
sort(cpy.begin(),cpy.end());
//checking if the given array is sorted or not
if(cpy==arr)
{
return 0;
}
else
{
//iterating the array
for(int i=0;i<=n-2;i++)
{
int min_val=arr[i];
int left=i;
int right=-1;
//now iterate from i+1 to n-1
for(int j=i+1;j<n;j++)
{
if(min_val>arr[j])
{
min_val=arr[j];
right=j;
}
}
//checking if cyclic shift is required or not
if(right!=-1)
{
int k=right;
int tmp=arr[right];
//cyclic shift from left to right
while(k>left)
{
arr[k]=arr[k-1];
k--;
}
arr[k]=tmp;
//cyclic shift occurred
count++;
}
}
}
return count;
}
//driver code
int main()
{
vector<int> arr{4,3,2,1};
cout<<"no of cyclic shift occurred: "<<cyclicShiftSort(arr,4)<<endl;
}

Output

no of cyclic shift occurred: 3

Complexity

In the worst-case, the time complexity of the above approach is O(n2) and space complexity is O(1) as no extra space is required for the above implementation.

FAQs

What is a cyclic shift on any subarray? It means to separate out a subarray from the given array and apply cyclic shift or rotation on the subarray by any offset and then put it back to the same position.

What are different sorting algorithms commonly used? The most commonly used sorting algorithms are Quick sort Merge sort Bubble sort Insertion sort Heap sort Radix sort

Key Takeaways

This article covered how to sort a given array using at most n cyclic shift on any subarray.

Check out the Coding Ninjas Studio library for getting a better hold of the data structures and algorithms.

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here.