Posted on by Kalkicode
Code Array

# 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

1. The `reverse` function takes an array and the starting and ending indices of a subarray as parameters. It swaps elements between `start` and `end` indices to reverse the subarray.
2. The `sort_rotated` function takes the array and its size as parameters.
3. It iterates through the array to find the rotation count, similar to the rotation count finding logic.
4. 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.
5. 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 in `O(n)` time, where `n` is the size of the subarray.
• The `sort_rotated` function involves three calls to the `reverse` function, each with a different subarray size. Therefore, the time complexity of the overall algorithm is `O(n)`.

## Comment

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.

Categories
Relative Post