Last Updated: 6 Jan, 2021
Sorting Of A Rotated Sorted Array
Easy
Asked in companies
Given a rotated sorted array of size ‘N’ and let the elements of the given array be a1,a2,......,an . You need to sort the given array in increasing order.
For Example - Consider ‘N’ = 4 and the given array is [2,3,4,1] then the output should be [1,2,3,4].
A rotated sorted array is a sorted array in which each element is shifted ‘x’ (‘x’ >= 0 and ‘x’ <= ’N’) times to its right and the rightmost element is shifted to the beginning of the array.
For Example - [3,4,1,2] is a rotated sorted array in which each element is shifted two times to its right.
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first line of each test case contains an integer ‘N’ denoting the size of the given rotated sorted array.
The second line of each test case contains ‘N’ single space-separated integers denoting the elements of the given rotated sorted array.
Output Format :
For each test case, print a single line containing 'N' single space-separated integers representing the elements of the sorted array.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
1 <= N <= 10^4
-10^9 <= a[i] <= 10^9
Where ‘T’ is the total number of test cases, ‘N’ is the size of the array and a[i] is an element of the array.
Time Limit: 1 sec
Follow up :
Don’t use the sort() function.
Approaches
- Find the rotation point is the rotated array using linear search and store its index in a variable ‘shiftCount’.
- Run a while loop ‘shiftCount’ times and in each iteration do the following:
- Store the element at index 0 in variable ‘leftElement’
- Shift each element with index > 0 to its left.
- Store the element stored in ‘leftElement at the last index.
Before Iteration
After Iteration
- Find the rotation point is the rotated array using linear search and store its index in a variable ‘pivot’.
- Reverse the array in following three stages
- Reverse the array starting index to ‘pivot’-1.
- Reverse the array from ‘pivot’ to ending index.
- Reverse the array from starting index to ending index.
- After the first two reversals we will have the array in decreasing order so we need to reverse the array one more time.
- Find the rotation point is the rotated array using binary search and store its index in a variable ‘pivot’.
- Reverse the array in following three stages
- Reverse the array starting index to ‘pivot’-1.
- Reverse the array from ‘pivot’ to ending index.
- Reverse the array from starting index to ending index.
- After the first two reversals we will have the array in decreasing order so we need to reverse the array one more time.
Similar problems