Sort given Array using at most N cyclic shift on any subarray

Approach

Here we will be using the brute force approach to solve the problem.

So simply, first, we need to check if the given array is already sorted or not.

If sorted, 

no cyclic shift is required.

Otherwise(if not sorted), we need to follow below steps:

• create variables to store left and right pointer for a subarray, which needs cyclic shift for sorting.
• Start iterating the array, and for each element, store the left pointer as the current index i.
• Search for min_value less than the current value from i+1 to n.
• If such value is found, initialize the index of the element as the right pointer.
• Now apply a cyclic shift from left to the right position and increment the count by 1.
• After completion of the outer loop, the array will be sorted as desired. 

Also read, Euclid GCD Algorithm

Dry run

Code

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

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

1. 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. 
    
2. 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.

Recommended Problem - Merge K Sorted Arrays

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. 

Happy learning!