1.
Introduction
2.
Problem statement
3.
Approach
4.
Dry run
5.
Code
6.
Complexity
7.
FAQs
8.
Key Takeaways
Last Updated: Mar 27, 2024

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

Malay Gain
0 upvote

## Introduction

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.

The above illustration shows cyclic shift by offset 1 from starting index to the end index of the array.

## Problem statement

You are given an array of integers. Sort the array by at most n cyclic shiftings where n is the size of the array.

Input

arr[ ]={4,3,2,1}, n=4

Output

No of cyclic shift= 3

Note: Please try to solve the problem first and then see the solution below.

## 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.

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

## 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!

Live masterclass