Sort elements in sorted and rotated array
Sorting elements in a sorted and rotated array is a common problem in programming. In a rotated sorted array, an array that was originally sorted is rotated cyclically by an unknown number of positions. The task is to sort the elements in their original order.
Problem Statement
Given a rotated sorted array of distinct integers, sort the elements in their original order. The rotation count corresponds to the index of the smallest element in the rotated array.
Example
Consider the following rotated sorted array:
arr = [12, 32, 100, 103, 1, 4, 6, 8, 9, 12]
After sorting in their original order:
arr = [1, 4, 6, 8, 9, 12, 12, 32, 100, 103]
Idea to Solve
To solve this problem, we can utilize the same concept of reversing portions of the array as we did to find the rotation count. Once we identify the rotation count, we can reverse the subarrays to restore the original order of the elements.
Pseudocode
function reverse(arr, start, end):
while start < end:
swap arr[start] with arr[end]
start++
end--
function sort_rotated(arr, size):
i = 0
while i < size - 1 and arr[i] <= arr[i+1]:
i++
if i + 1 < size:
reverse(arr, 0, i)
reverse(arr, i+1, size-1)
reverse(arr, 0, size-1)
// Example usage
arr = [12, 32, 100, 103, 1, 4, 6, 8, 9, 12]
size = size(arr)
sort_rotated(arr, size)
print(arr)
Algorithm Explanation
- The
reverse
function takes an array and the starting and ending indices of a subarray as parameters. It swaps elements betweenstart
andend
indices to reverse the subarray. - The
sort_rotated
function takes the array and its size as parameters. - It iterates through the array to find the rotation count, similar to the rotation count finding logic.
- If a rotation count is found, it reverses the subarray before the rotation point, the subarray after the rotation point, and then the entire array.
- Reversing these subarrays effectively sorts the elements in their original order.
Code Solution
//C Program
//Sort elements in sorted and rotated array
#include <stdio.h>
void reverse(int arr[],int start,int end)
{
int temp=0;
for (int i = start,j=end; i <= end && j>i; ++i,--j)
{
//reverse the array element
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
//Sort the elements of rotated sorted array
void sort(int arr[],int size)
{
if(size<=1) {
return;
}
int i = 0;
//Find First largest element
while(i < size-1 && arr[i] <= arr[i+1])
{
i++;
}
if(i+1 < size)
{
//Reverse the array element
reverse(arr,0,i);
reverse(arr,i+1,size-1);
reverse(arr,0,size-1);
}
else
{
printf("Not an rotated sorted array\n");
}
}
//Display array element values
void dispay(int arr[],int size)
{
for (int i = 0; i < size; ++i)
{
printf("%d ",arr[i] );
}
printf("\n");
}
int main()
{
//define array elements
int arr[] ={12,32,100,103,1,4,6,8,9,12};
//Get the size of array
int size=(sizeof(arr)/sizeof(arr[0]));
dispay(arr,size);
sort(arr,size);
dispay(arr,size);
return 0;
}
Output
12 32 100 103 1 4 6 8 9 12
1 4 6 8 9 12 12 32 100 103
/*
C++ Program
Sort elements in sorted and rotated array
*/
#include<iostream>
using namespace std;
class MyArray {
public:
void reverse(int arr[], int first, int last) {
int temp = 0;
for (int i = first, j = last; i <= last && j > i; ++i, --j) {
//reverse the array element
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//Sort the elements of rotated sorted array
//Assume that given array is form of sorted and rotated
void sort(int arr[], int size) {
if (size <= 1) {
return;
}
int i = 0;
//Find First largest element
while (i < size - 1 && arr[i] <= arr[i + 1]) {
i++;
}
if (i + 1 < size) {
//Reverse the array element
this->reverse(arr, 0, i);
this->reverse(arr, i + 1, size - 1);
this->reverse(arr, 0, size - 1);
} else {
cout << "Not an rotated sorted array\n";
}
}
//Display array element values
void dispay(int arr[], int size) {
for (int i = 0; i < size; ++i) {
cout << " " << arr[i];
}
cout << "\n";
}
};
int main() {
MyArray obj = MyArray();
int arr[] = {
12,
32,
100,
103,
1,
4,
6,
8,
9,
12
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
obj.dispay(arr, size);
obj.sort(arr, size);
obj.dispay(arr, size);
return 0;
}
Output
12 32 100 103 1 4 6 8 9 12
1 4 6 8 9 12 12 32 100 103
/*
Java Program
Sort elements in sorted and rotated array
*/
public class MyArray
{
public void reverse(int []arr,int first,int last)
{
int temp=0;
for (int i = first,j=last; i <= last && j>i; ++i,--j)
{
//reverse the array element
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
//Sort the elements of rotated sorted array
//Assume that given array is form of sorted and rotated
public void sort(int []arr,int size)
{
if(size<=1) {
return;
}
int i = 0;
//Find First largest element
while(i < size-1 && arr[i] <= arr[i+1])
{
i++;
}
if(i+1 < size)
{
//Reverse the array element
reverse(arr,0,i);
reverse(arr,i+1,size-1);
reverse(arr,0,size-1);
}
else
{
System.out.print("Not an rotated sorted array\n");
}
}
//Display array element values
void dispay(int []arr,int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" "+arr[i] );
}
System.out.print("\n");
}
public static void main(String[] args) {
MyArray obj = new MyArray();
//Define the value of array elements
int []arr = {12,32,100,103,1,4,6,8,9,12};
//Get the size of array
int size = arr.length;
obj.dispay(arr,size);
obj.sort(arr,size);
obj.dispay(arr,size);
}
}
Output
12 32 100 103 1 4 6 8 9 12
1 4 6 8 9 12 12 32 100 103
/*
C# Program
Sort elements in sorted and rotated array
*/
using System;
public class MyArray {
public void reverse(int[] arr, int first, int last) {
int temp = 0;
for (int i = first, j = last; i <= last && j > i; ++i, --j) {
//reverse the array element
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//Sort the elements of rotated sorted array
//Assume that given array is form of sorted and rotated
public void sort(int[] arr, int size) {
if (size <= 1) {
return;
}
int i = 0;
//Find First largest element
while (i < size - 1 && arr[i] <= arr[i + 1]) {
i++;
}
if (i + 1 < size) {
reverse(arr, 0, i);
reverse(arr, i + 1, size - 1);
reverse(arr, 0, size - 1);
} else {
Console.Write("Not an rotated sorted array\n");
}
}
//Display array element values
void dispay(int[] arr, int size) {
for (int i = 0; i < size; ++i) {
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
int[]
//Define the value of array elements
arr = {
12,
32,
100,
103,
1,
4,
6,
8,
9,
12
};
//Get the size of array
int size = arr.Length;
obj.dispay(arr, size);
obj.sort(arr, size);
obj.dispay(arr, size);
}
}
Output
12 32 100 103 1 4 6 8 9 12
1 4 6 8 9 12 12 32 100 103
<?php
/*
Php Program
Sort elements in sorted and rotated array
*/
class MyArray {
public function reverse(&$arr, $first, $last) {
$temp = 0;
for ($i = $first, $j = $last; $i <= $last && $j > $i; ++$i, --$j) {
//reverse the array element
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}
}
//Sort the elements of rotated sorted array
//Assume that given array is form of sorted and rotated
public function sort(&$arr, $size) {
if ($size <= 1) {
return;
}
$i = 0;
//Find First largest element
while ($i < $size - 1 && $arr[$i] <= $arr[$i + 1]) {
$i++;
}
if ($i + 1 < $size) {
//Reverse the array element
$this->reverse($arr, 0, $i);
$this->reverse($arr, $i + 1, $size - 1);
$this->reverse($arr, 0, $size - 1);
} else {
echo("Not an rotated sorted array\n");
}
}
//Display array element values
function dispay($arr, $size) {
for ($i = 0; $i < $size; ++$i) {
echo(" ". $arr[$i]);
}
echo("\n");
}
}
function main() {
$obj = new MyArray();
//Define the value of array elements
$arr = array(12, 32, 100, 103, 1, 4, 6, 8, 9, 12);
//Get the size of array
$size = count($arr);
$obj->dispay($arr, $size);
$obj->sort($arr, $size);
$obj->dispay($arr, $size);
}
main();
Output
12 32 100 103 1 4 6 8 9 12
1 4 6 8 9 12 12 32 100 103
/*
Node Js Program
Sort elements in sorted and rotated array
*/
class MyArray {
reverse(arr, first, last) {
var temp = 0;
for (var i = first, j = last; i <= last && j > i; ++i, --j) {
//reverse the array element
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//Sort the elements of rotated sorted array
//Assume that given array is form of sorted and rotated
sort(arr, size) {
if (size <= 1) {
return;
}
var i = 0;
//Find First largest element
while (i < size - 1 && arr[i] <= arr[i + 1]) {
i++;
}
if (i + 1 < size) {
//Reverse the array element
this.reverse(arr, 0, i);
this.reverse(arr, i + 1, size - 1);
this.reverse(arr, 0, size - 1);
} else {
process.stdout.write("Not an rotated sorted array\n");
}
}
//Display array element values
dispay(arr, size) {
for (var i = 0; i < size; ++i) {
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
}
function main(args) {
var obj = new MyArray();
//Define the value of array elements
var arr = [12, 32, 100, 103, 1, 4, 6, 8, 9, 12];
//Get the size of array
var size = arr.length;
obj.dispay(arr, size);
obj.sort(arr, size);
obj.dispay(arr, size);
}
main();
Output
12 32 100 103 1 4 6 8 9 12
1 4 6 8 9 12 12 32 100 103
# Python 3 Program
# Sort elements in sorted and rotated array
class MyArray :
def reverse(self, arr, first, last) :
temp = 0
i = first
j = last
while (i <= last and j > i) :
# reverse the array element
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
i += 1
j -= 1
# Sort the elements of rotated sorted array
# Assume that given array is form of sorted and rotated
def sort(self, arr, size) :
if (size <= 1) :
return
i = 0
# Find First largest element
while (i < size - 1 and arr[i] <= arr[i + 1]) :
i += 1
if (i + 1 < size) :
self.reverse(arr, 0, i)
self.reverse(arr, i + 1, size - 1)
self.reverse(arr, 0, size - 1)
else :
print("Not an rotated sorted array\n", end = "")
def dispay(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
print("\n", end = "")
def main() :
obj = MyArray()
arr = [12, 32, 100, 103, 1, 4, 6, 8, 9, 12]
size = len(arr)
obj.dispay(arr, size)
obj.sort(arr, size)
obj.dispay(arr, size)
if __name__ == "__main__":
main()
Output
12 32 100 103 1 4 6 8 9 12
1 4 6 8 9 12 12 32 100 103
# Ruby Program
# Sort elements in sorted and rotated array
class MyArray
def reverse(arr, first, last)
temp = 0
i = first
j = last
while (i <= last && j > i)
# reverse the array element
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
i += 1
j -= 1
end
end
# Sort the elements of rotated sorted array
# Assume that given array is form of sorted and rotated
def sort(arr, size)
if (size <= 1)
return
end
i = 0
# Find First largest element
while (i < size - 1 && arr[i] <= arr[i + 1])
i += 1
end
if (i + 1 < size)
self.reverse(arr, 0, i)
self.reverse(arr, i + 1, size - 1)
self.reverse(arr, 0, size - 1)
else
print("Not an rotated sorted array\n")
end
end
def dispay(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
end
def main()
obj = MyArray.new()
arr = [12, 32, 100, 103, 1, 4, 6, 8, 9, 12]
size = arr.length
obj.dispay(arr, size)
obj.sort(arr, size)
obj.dispay(arr, size)
end
main()
Output
12 32 100 103 1 4 6 8 9 12
1 4 6 8 9 12 12 32 100 103
/*
Scala Program
Sort elements in sorted and rotated array
*/
class MyArray {
def reverse(arr: Array[Int], first: Int, last: Int): Unit = {
var temp: Int = 0;
var i: Int = first;
var j: Int = last;
while (i <= last && j > i) {
//reverse the array element
temp = arr(i);
arr(i) = arr(j);
arr(j) = temp;
i += 1;
j -= 1;
}
}
//Sort the elements of rotated sorted array
//Assume that given array is form of sorted and rotated
def sort(arr: Array[Int], size: Int): Unit = {
if (size <= 1) {
return;
}
var i: Int = 0;
//Find First largest element
while (i < size - 1 && arr(i) <= arr(i + 1)) {
i += 1;
}
if (i + 1 < size) {
this.reverse(arr, 0, i);
this.reverse(arr, i + 1, size - 1);
this.reverse(arr, 0, size - 1);
} else {
print("Not an rotated sorted array\n");
}
}
def dispay(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size) {
print(" " + arr(i));
i += 1;
}
print("\n");
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyArray = new MyArray();
var arr: Array[Int] = Array(12, 32, 100, 103, 1, 4, 6, 8, 9, 12);
val size: Int = arr.length;
obj.dispay(arr, size);
obj.sort(arr, size);
obj.dispay(arr, size);
}
}
Output
12 32 100 103 1 4 6 8 9 12
1 4 6 8 9 12 12 32 100 103
/*
Swift Program
Sort elements in sorted and rotated array
*/
class MyArray {
func reverse(_ arr: inout [Int], _ first: Int, _ last: Int) {
var temp: Int = 0;
var i: Int = first;
var j: Int = last;
while (i <= last && j > i) {
//reverse the array element
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i += 1;
j -= 1;
}
}
//Sort the elements of rotated sorted array
//Assume that given array is form of sorted and rotated
func sort(_ arr: inout [Int], _ size: Int) {
if (size <= 1) {
return;
}
var i: Int = 0;
//Find First largest element
while (i < size - 1 && arr[i] <= arr[i + 1]) {
i += 1;
}
if (i + 1 < size) {
self.reverse(&arr, 0, i);
self.reverse(&arr, i + 1, size - 1);
self.reverse(&arr, 0, size - 1);
} else {
print("Not an rotated sorted array\n", terminator: "");
}
}
func dispay(_ arr: [Int], _ size: Int) {
var i: Int = 0;
while (i < size) {
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
}
func main() {
let obj: MyArray = MyArray();
var arr: [Int] = [12, 32, 100, 103, 1, 4, 6, 8, 9, 12];
let size: Int = arr.count;
obj.dispay(arr, size);
obj.sort(&arr, size);
obj.dispay(arr, size);
}
main();
Output
12 32 100 103 1 4 6 8 9 12
1 4 6 8 9 12 12 32 100 103
Time Complexity
- The
reverse
function runs inO(n)
time, wheren
is the size of the subarray. - The
sort_rotated
function involves three calls to thereverse
function, each with a different subarray size. Therefore, the time complexity of the overall algorithm isO(n)
.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment