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
• C++
• Java
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

//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;
}

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;
}

 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);
  }
}

 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);
	}
}

 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();

 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();

 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()

  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()

 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);
	}
}

 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();

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