Introduction
Suppose we have a rotated sorted array of distinct elements, i.e., a sorted array rotated around some pivot. Now we are asked to restore the sorted array. Let's look at an example to understand this problem. 
In the above example, the initial array is a rotated sorted array, i.e., it is a sorted array rotated by three positions towards the left. Now, our task is to find the initially sorted array.
Though there could be numerous methods to solve this problem, we will focus on the two most commonly used ones. The first is a brute approach based on finding the pivot using linear search, splitting the array around it, reversing the subarrays, then reversing the whole array to get the sorted array.
The second method is the optimization of the first method. In this method, we use binary search to find the array's pivot element. Then split and reverse the arrays, as we did in the first method. Let's understand these methods one by one-
Also see, Array Implementation of Queue and Rabin Karp Algorithm
The basic solution
The basic solution of this problem starts with finding the pivot of the array. To do so, we use Linear search in which we traverse the array from left to right and check each element if it is smaller than its predecessor. After finding the pivot, we split the array into two subarrays. Left subarray from the first element to the predecessor of the pivot element. Right subarray from the pivot element to the last element of the array. Then we first reverse these subarrays, after which we reverse the whole array to get the initially sorted array.
Algorithm
- Take the array and key from user input.
- Traverse the array to find the pivot element
- call the reverse function in the following order-
- From the 0th index to (pivot-1) index
- From the (pivot) index to the last index.
- From the 0th index to the last index.
- Print the array.
Implementation of the basic approach
|
#include <bits/stdc++.h> using namespace std; //Function to sort the array. void sortarray(int ar[], int n) { //Linear search to find the pivot element in the array. //After that reverse the arrays. for (int i = 0; i < n; i++) { if (ar[i]>ar[i+1]) { reverse(ar, ar+i+1); reverse(ar + i + 1, ar + n); reverse(ar, ar + n); } } } //Driver function. int main() { //Taking array size and key as input. int n, k; cout<<"Enter the number of elements in the array"<<endl; cin>>n; //Declaring the array. int ar[n]; cout<<"Enter array elements-"<<endl; //Taking input in the array. for(int i=0;i<n;i++) { cin>>ar[i]; } //Function call. sortarray(ar,n); //Printing the result. for(int i=0;i<n;i++) { cout<<ar[i]<<" "; } return 0; } |
Input-
|
Enter the number of elements in the array 7 Enter array elements- 10 11 12 6 7 8 9 |
Output-
| 6 7 8 9 10 11 12 |
The time complexity of this algorithm is O(N), as we are using binary search.
The space complexity of this algorithm is O(1), as no extra space is required.
8+ registered 