Skip to main content

Sort a rotated sorted array

Here given code implementation process.

// C program 
// Sort a rotated sorted array
#include <stdio.h>

//Function which is swapping two array elements of given location
void swapElement(int arr[], int i, int j)
{
	//Get i location element
	int temp = arr[i];
	//set new values
	arr[i] = arr[j];
	arr[j] = temp;
}
//Function which is Reversing given array elements 
void reverseElement(int arr[], int a, int b)
{
	int front = a;
	int tail = b;
	while (front < tail)
	{
		//Swap the array elements
		swapElement(arr, front, tail);
		front++;
		tail--;
	}
}
// Handles the request to sort an given of sorted and rotated array
void sortRotatedArray(int arr[], int size)
{
	if (size <= 0)
	{
		return;
	}
	int i = 0;
	// Find largest element in rotated array
	while (i + 1 < size && arr[i] <= arr[i + 1])
	{
		i++;
	}
	if (i >= size - 1)
	{
		// When array is already sorted
		return;
	}
	// Reverse the array element from index 0 to maximum element 
	reverseElement(arr, 0, i);
	// Reverse the array element from index 
	// maximum element location+1 to size-1
	reverseElement(arr, i + 1, size - 1);
	// Reverse entire array
	reverseElement(arr, 0, size - 1);
}
//Function which is display array elements
void display(int arr[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf("%d  ", arr[i]);
	}
	printf("\n");
}
int main()
{
	// Define the rotated sorted arrays
	int arr1[] = {
		6 , 7 , 8 , 9 , 1 , 2 , 4 , 5
	};
	int arr2[] = {
		9 , 11 , 1 , 3 , 6 , 8 , 8 , 9
	};
	// Get the size
	int size = sizeof(arr1) / sizeof(arr1[0]);
	// Just before the Sort rotated sorted array elements
	printf("Before Sort elements \n");
	display(arr1, size);
	sortRotatedArray(arr1, size);
	// After modify array elements
	printf("After Sort elements \n");
	display(arr1, size);
	// Get the size
	size = sizeof(arr2) / sizeof(arr2[0]);
	// Just before the Sort rotated sorted array elements
	printf("\nBefore Sort elements \n");
	display(arr2, size);
	sortRotatedArray(arr2, size);
	// After modify array elements
	printf("After Sort elements \n");
	display(arr2, size);
	return 0;
}

Output

Before Sort elements
6  7  8  9  1  2  4  5
After Sort elements
1  2  4  5  6  7  8  9

Before Sort elements
9  11  1  3  6  8  8  9
After Sort elements
1  3  6  8  8  9  9  11
/*
   Java Program
   Sort a rotated sorted array
*/
public class SortArray
{
	//Function which is swapping two array elements of given location
	public void swapElement(int[] arr, int i, int j)
	{
		//Get i location element
		int temp = arr[i];
		//set new values
		arr[i] = arr[j];
		arr[j] = temp;
	}
	//Function which is Reversing given array elements 
	public void reverseElement(int[] arr, int a, int b)
	{
		int front = a;
		int tail = b;
		while (front < tail)
		{
			//Swap array elements
			swapElement(arr, front, tail);
			front++;
			tail--;
		}
	}
	// Handles the request to sort an given of sorted and rotated array
	public void sortRotatedArray(int[] arr, int size)
	{
		if (size <= 0)
		{
			return;
		}
		int i = 0;
		// Find largest element in rotated array
		while (i + 1 < size && arr[i] <= arr[i + 1])
		{
			i++;
		}
		if (i >= size - 1)
		{
			// When array is already sorted
			return;
		}
		// Reverse the array element from index 0 to maximum element 
		reverseElement(arr, 0, i);
		// Reverse the array element from index 
		// maximum element location+1 to size-1
		reverseElement(arr, i + 1, size - 1);
		// Reverse entire array
		reverseElement(arr, 0, size - 1);
	}
	//Function which is display array elements
	public void display(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)
	{
		SortArray task = new SortArray();
		// Define the rotated sorted arrays
		int[] arr1 = {
			6 , 7 , 8 , 9 , 1 , 2 , 4 , 5
		};
		int[] arr2 = {
			9 , 11 , 1 , 3 , 6 , 8 , 8 , 9
		};
		// Get the size
		int size = arr1.length;
		// Just before the Sort rotated sorted array elements
		System.out.print("Before Sort elements \n");
		task.display(arr1, size);
		/*
		Before Sort
		{ 6 , 7 , 8 , 9 , 1 , 2 , 4 , 5 }
		After Sort
		{ 1, 2, 4, 5, 6, 7, 8, 9}
		*/
		task.sortRotatedArray(arr1, size);
		// After modify array elements
		System.out.print("After Sort elements \n");
		task.display(arr1, size);
		// Get the size
		size = arr2.length;
		// Just before the Sort rotated sorted array elements
		System.out.print("\nBefore Sort elements \n");
		task.display(arr2, size);
		/*
		Before Sort
		{ 9 , 11 , 1 , 3 , 6 , 8 , 8 , 9}
		After Sort
		{ 1, 3, 6, 8, 8, 9, 9, 11}
		*/
		task.sortRotatedArray(arr2, size);
		// After modify array elements
		System.out.print("After Sort elements \n");
		task.display(arr2, size);
	}
}

Output

Before Sort elements
  6  7  8  9  1  2  4  5
After Sort elements
  1  2  4  5  6  7  8  9

Before Sort elements
  9  11  1  3  6  8  8  9
After Sort elements
  1  3  6  8  8  9  9  11
// Include header file
#include <iostream>

using namespace std;
/*
   C++ Program
   Sort a rotated sorted array
*/
class SortArray
{
    public:
        //Function which is swapping two array elements of given location
        void swapElement(int arr[], int i, int j)
        {
            //Get i location element
            int temp = arr[i];
            //set new values
            arr[i] = arr[j];
            arr[j] = temp;
        }
    //Function which is Reversing given array elements
    void reverseElement(int arr[], int a, int b)
    {
        int front = a;
        int tail = b;
        while (front < tail)
        {
            //Swap array elements
            this->swapElement(arr, front, tail);
            front++;
            tail--;
        }
    }
    // Handles the request to sort an given of sorted and rotated array
    void sortRotatedArray(int arr[], int size)
    {
        if (size <= 0)
        {
            return;
        }
        int i = 0;
        // Find largest element in rotated array
        while (i + 1 < size && arr[i] <= arr[i + 1])
        {
            i++;
        }
        // When array is already sorted
        if (i >= size - 1)
        {
            return;
        }
        // Reverse the array element from index 0 to maximum element
        this->reverseElement(arr, 0, i);
        // Reverse the array element from index
        // maximum element location+1 to size-1
        this->reverseElement(arr, i + 1, size - 1);
        // Reverse entire array
        this->reverseElement(arr, 0, size - 1);
    }
    //Function which is display array elements
    void display(int arr[], int size)
    {
        for (int i = 0; i < size; ++i)
        {
            cout << "  " << arr[i];
        }
        cout << "\n";
    }
};
int main()
{
    SortArray task = SortArray();
    // Define the rotated sorted arrays
    int arr1[] = {
        6 , 7 , 8 , 9 , 1 , 2 , 4 , 5
    };
    int arr2[] = {
        9 , 11 , 1 , 3 , 6 , 8 , 8 , 9
    };
    // Get the size
    int size = sizeof(arr1) / sizeof(arr1[0]);
    // Just before the Sort rotated sorted array elements
    cout << "Before Sort elements \n";
    task.display(arr1, size);
    /*
    Before Sort
    { 6 , 7 , 8 , 9 , 1 , 2 , 4 , 5 }
    After Sort
    { 1, 2, 4, 5, 6, 7, 8, 9}
    */
    task.sortRotatedArray(arr1, size);
    // After modify array elements
    cout << "After Sort elements \n";
    task.display(arr1, size);
    // Get the size
    size = sizeof(arr2) / sizeof(arr2[0]);
    // Just before the Sort rotated sorted array elements
    cout << "\nBefore Sort elements \n";
    task.display(arr2, size);
    /*
    Before Sort
    { 9 , 11 , 1 , 3 , 6 , 8 , 8 , 9}
    After Sort
    { 1, 3, 6, 8, 8, 9, 9, 11}
    */
    task.sortRotatedArray(arr2, size);
    // After modify array elements
    cout << "After Sort elements \n";
    task.display(arr2, size);
    return 0;
}

Output

Before Sort elements
  6  7  8  9  1  2  4  5
After Sort elements
  1  2  4  5  6  7  8  9

Before Sort elements
  9  11  1  3  6  8  8  9
After Sort elements
  1  3  6  8  8  9  9  11
// Include namespace system
using System;
/*
   C# Program
   Sort a rotated sorted array
*/
public class SortArray
{
    //Function which is swapping two array elements of given location
    public void swapElement(int[] arr, int i, int j)
    {
        //Get i location element
        int temp = arr[i];
        //set new values
        arr[i] = arr[j];
        arr[j] = temp;
    }
    //Function which is Reversing given array elements
    public void reverseElement(int[] arr, int a, int b)
    {
        int front = a;
        int tail = b;
        while (front < tail)
        {
            //Swap array elements
            swapElement(arr, front, tail);
            front++;
            tail--;
        }
    }
    // Handles the request to sort an given of sorted and rotated array
    public void sortRotatedArray(int[] arr, int size)
    {
        if (size <= 0)
        {
            return;
        }
        int i = 0;
        // Find largest element in rotated array
        while (i + 1 < size && arr[i] <= arr[i + 1])
        {
            i++;
        }
        // When array is already sorted
        if (i >= size - 1)
        {
            return;
        }
        // Reverse the array element from index 0 to maximum element
        reverseElement(arr, 0, i);
        // Reverse the array element from index
        // maximum element location+1 to size-1
        reverseElement(arr, i + 1, size - 1);
        // Reverse entire array
        reverseElement(arr, 0, size - 1);
    }
    //Function which is display array elements
    public void display(int[] arr, int size)
    {
        for (int i = 0; i < size; ++i)
        {
            Console.Write("  " + arr[i]);
        }
        Console.Write("\n");
    }
    public static void Main(String[] args)
    {
        SortArray task = new SortArray();
        // Define the rotated sorted arrays
        int[] arr1 = {
            6 , 7 , 8 , 9 , 1 , 2 , 4 , 5
        };
        int[] arr2 = {
            9 , 11 , 1 , 3 , 6 , 8 , 8 , 9
        };
        // Get the size
        int size = arr1.Length;
        // Just before the Sort rotated sorted array elements
        Console.Write("Before Sort elements \n");
        task.display(arr1, size);
        /*
        Before Sort
        { 6 , 7 , 8 , 9 , 1 , 2 , 4 , 5 }
        After Sort
        { 1, 2, 4, 5, 6, 7, 8, 9}
        */
        task.sortRotatedArray(arr1, size);
        // After modify array elements
        Console.Write("After Sort elements \n");
        task.display(arr1, size);
        // Get the size
        size = arr2.Length;
        // Just before the Sort rotated sorted array elements
        Console.Write("\nBefore Sort elements \n");
        task.display(arr2, size);
        /*
        Before Sort
        { 9 , 11 , 1 , 3 , 6 , 8 , 8 , 9}
        After Sort
        { 1, 3, 6, 8, 8, 9, 9, 11}
        */
        task.sortRotatedArray(arr2, size);
        // After modify array elements
        Console.Write("After Sort elements \n");
        task.display(arr2, size);
    }
}

Output

Before Sort elements
  6  7  8  9  1  2  4  5
After Sort elements
  1  2  4  5  6  7  8  9

Before Sort elements
  9  11  1  3  6  8  8  9
After Sort elements
  1  3  6  8  8  9  9  11
<?php
/*
   Php Program
   Sort a rotated sorted array
*/
class SortArray
{
    //Function which is swapping two array elements of given location
    public  function swapElement( & $arr, $i, $j)
    {
        //Get i location element
        $temp = $arr[$i];
        //set new values
        $arr[$i] = $arr[$j];
        $arr[$j] = $temp;
    }
    //Function which is Reversing given array elements
    public  function reverseElement( & $arr, $a, $b)
    {
        $front = $a;
        $tail = $b;
        while ($front < $tail)
        {
            //Swap array elements
            $this->swapElement($arr, $front, $tail);
            $front++;
            $tail--;
        }
    }
    // Handles the request to sort an given of sorted and rotated array
    public  function sortRotatedArray( & $arr, $size)
    {
        if ($size <= 0)
        {
            return;
        }
        $i = 0;
        // Find largest element in rotated array
        while ($i + 1 < $size && $arr[$i] <= $arr[$i + 1])
        {
            $i++;
        }
        // When array is already sorted
        if ($i >= $size - 1)
        {
            return;
        }
        // Reverse the array element from index 0 to maximum element
        $this->reverseElement($arr, 0, $i);
        // Reverse the array element from index
        // maximum element location+1 to size-1
        $this->reverseElement($arr, $i + 1, $size - 1);
        // Reverse entire array
        $this->reverseElement($arr, 0, $size - 1);
    }
    //Function which is display array elements
    public  function display( & $arr, $size)
    {
        for ($i = 0; $i < $size; ++$i)
        {
            echo "  ". $arr[$i];
        }
        echo "\n";
    }
}

function main()
{
    $task = new SortArray();
    // Define the rotated sorted arrays
    $arr1 = array(6, 7, 8, 9, 1, 2, 4, 5);
    $arr2 = array(9, 11, 1, 3, 6, 8, 8, 9);
    // Get the size
    $size = count($arr1);
    // Just before the Sort rotated sorted array elements
    echo "Before Sort elements \n";
    $task->display($arr1, $size);
    /*
    Before Sort
    { 6 , 7 , 8 , 9 , 1 , 2 , 4 , 5 }
    After Sort
    { 1, 2, 4, 5, 6, 7, 8, 9}
    */
    $task->sortRotatedArray($arr1, $size);
    // After modify array elements
    echo "After Sort elements \n";
    $task->display($arr1, $size);
    // Get the size
    $size = count($arr2);
    // Just before the Sort rotated sorted array elements
    echo "\nBefore Sort elements \n";
    $task->display($arr2, $size);
    /*
    Before Sort
    { 9 , 11 , 1 , 3 , 6 , 8 , 8 , 9}
    After Sort
    { 1, 3, 6, 8, 8, 9, 9, 11}
    */
    $task->sortRotatedArray($arr2, $size);
    // After modify array elements
    echo "After Sort elements \n";
    $task->display($arr2, $size);
}
main();

Output

Before Sort elements
  6  7  8  9  1  2  4  5
After Sort elements
  1  2  4  5  6  7  8  9

Before Sort elements
  9  11  1  3  6  8  8  9
After Sort elements
  1  3  6  8  8  9  9  11
/*
   Node Js Program
   Sort a rotated sorted array
*/
class SortArray
{
    //Function which is swapping two array elements of given location
    swapElement(arr, i, j)
    {
        //Get i location element
        var temp = arr[i];
        //set new values
        arr[i] = arr[j];
        arr[j] = temp;
    }
    //Function which is Reversing given array elements
    reverseElement(arr, a, b)
    {
        var front = a;
        var tail = b;
        while (front < tail)
        {
            //Swap array elements
            this.swapElement(arr, front, tail);
            front++;
            tail--;
        }
    }
    // Handles the request to sort an given of sorted and rotated array
    sortRotatedArray(arr, size)
    {
        if (size <= 0)
        {
            return;
        }
        var i = 0;
        // Find largest element in rotated array
        while (i + 1 < size && arr[i] <= arr[i + 1])
        {
            i++;
        }
        // When array is already sorted
        if (i >= size - 1)
        {
            return;
        }
        // Reverse the array element from index 0 to maximum element
        this.reverseElement(arr, 0, i);
        // Reverse the array element from index
        // maximum element location+1 to size-1
        this.reverseElement(arr, i + 1, size - 1);
        // Reverse entire array
        this.reverseElement(arr, 0, size - 1);
    }
    //Function which is display array elements
    display(arr, size)
    {
        for (var i = 0; i < size; ++i)
        {
            process.stdout.write("  " + arr[i]);
        }
        process.stdout.write("\n");
    }
}

function main()
{
    var task = new SortArray();
    // Define the rotated sorted arrays
    var arr1 = [6, 7, 8, 9, 1, 2, 4, 5];
    var arr2 = [9, 11, 1, 3, 6, 8, 8, 9];
    // Get the size
    var size = arr1.length;
    // Just before the Sort rotated sorted array elements
    process.stdout.write("Before Sort elements \n");
    task.display(arr1, size);
    /*
    Before Sort
    { 6 , 7 , 8 , 9 , 1 , 2 , 4 , 5 }
    After Sort
    { 1, 2, 4, 5, 6, 7, 8, 9}
    */
    task.sortRotatedArray(arr1, size);
    // After modify array elements
    process.stdout.write("After Sort elements \n");
    task.display(arr1, size);
    // Get the size
    size = arr2.length;
    // Just before the Sort rotated sorted array elements
    process.stdout.write("\nBefore Sort elements \n");
    task.display(arr2, size);
    /*
    Before Sort
    { 9 , 11 , 1 , 3 , 6 , 8 , 8 , 9}
    After Sort
    { 1, 3, 6, 8, 8, 9, 9, 11}
    */
    task.sortRotatedArray(arr2, size);
    // After modify array elements
    process.stdout.write("After Sort elements \n");
    task.display(arr2, size);
}
main();

Output

Before Sort elements
  6  7  8  9  1  2  4  5
After Sort elements
  1  2  4  5  6  7  8  9

Before Sort elements
  9  11  1  3  6  8  8  9
After Sort elements
  1  3  6  8  8  9  9  11
#  Python 3 Program
#  Sort a rotated sorted array

class SortArray :
	# Function which is swapping two array elements of given location
	def swapElement(self, arr, i, j) :
		# Get i location element
		temp = arr[i]
		# set new values
		arr[i] = arr[j]
		arr[j] = temp
	
	# Function which is Reversing given array elements
	def reverseElement(self, arr, a, b) :
		front = a
		tail = b
		while (front < tail) :
			# Swap array elements
			self.swapElement(arr, front, tail)
			front += 1
			tail -= 1
		
	
	#  Handles the request to sort an given of sorted and rotated array
	def sortRotatedArray(self, arr, size) :
		if (size <= 0) :
			return
		
		i = 0
		#  Find largest element in rotated array
		while (i + 1 < size and arr[i] <= arr[i + 1]) :
			i += 1
		
		#  When array is already sorted
		if (i >= size - 1) :
			return
		
		#  Reverse the array element from index 0 to maximum element
		self.reverseElement(arr, 0, i)
		#  Reverse the array element from index
		#  maximum element location+1 to size-1
		self.reverseElement(arr, i + 1, size - 1)
		#  Reverse entire array
		self.reverseElement(arr, 0, size - 1)
	
	# Function which is display array elements
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print("  ", arr[i], end = "")
			i += 1
		
		print(end = "\n")
	

def main() :
	task = SortArray()
	#  Define the rotated sorted arrays
	arr1 = [6, 7, 8, 9, 1, 2, 4, 5]
	arr2 = [9, 11, 1, 3, 6, 8, 8, 9]
	#  Get the size
	size = len(arr1)
	#  Just before the Sort rotated sorted array elements
	print("Before Sort elements ")
	task.display(arr1, size)
	# 
	# 		Before Sort
	# 		: 6 , 7 , 8 , 9 , 1 , 2 , 4 , 5 
	# 		After Sort
	# 		: 1, 2, 4, 5, 6, 7, 8, 9
	# 		
	
	task.sortRotatedArray(arr1, size)
	#  After modify array elements
	print("After Sort elements ")
	task.display(arr1, size)
	#  Get the size
	size = len(arr2)
	#  Just before the Sort rotated sorted array elements
	print("\nBefore Sort elements ")
	task.display(arr2, size)
	# 
	# 		Before Sort
	# 		: 9 , 11 , 1 , 3 , 6 , 8 , 8 , 9
	# 		After Sort
	# 		: 1, 3, 6, 8, 8, 9, 9, 11
	# 		
	
	task.sortRotatedArray(arr2, size)
	#  After modify array elements
	print("After Sort elements ")
	task.display(arr2, size)

if __name__ == "__main__": main()

Output

Before Sort elements
   6   7   8   9   1   2   4   5
After Sort elements
   1   2   4   5   6   7   8   9

Before Sort elements
   9   11   1   3   6   8   8   9
After Sort elements
   1   3   6   8   8   9   9   11
#  Ruby Program
#  Sort a rotated sorted array

class SortArray 
	# Function which is swapping two array elements of given location
	def swapElement(arr, i, j) 
		# Get i location element
		temp = arr[i]
		# set new values
		arr[i] = arr[j]
		arr[j] = temp
	end

	# Function which is Reversing given array elements
	def reverseElement(arr, a, b) 
		front = a
		tail = b
		while (front < tail) 
			# Swap array elements
			self.swapElement(arr, front, tail)
			front += 1
			tail -= 1
		end

	end

	#  Handles the request to sort an given of sorted and rotated array
	def sortRotatedArray(arr, size) 
		if (size <= 0) 
			return
		end

		i = 0
		#  Find largest element in rotated array
		while (i + 1 < size && arr[i] <= arr[i + 1]) 
			i += 1
		end

		#  When array is already sorted
		if (i >= size - 1) 
			return
		end

		#  Reverse the array element from index 0 to maximum element
		self.reverseElement(arr, 0, i)
		#  Reverse the array element from index
		#  maximum element location+1 to size-1
		self.reverseElement(arr, i + 1, size - 1)
		#  Reverse entire array
		self.reverseElement(arr, 0, size - 1)
	end

	# Function which is display array elements
	def display(arr, size) 
		i = 0
		while (i < size) 
			print("  ", arr[i])
			i += 1
		end

		print("\n")
	end

end

def main() 
	task = SortArray.new()
	#  Define the rotated sorted arrays
	arr1 = [6, 7, 8, 9, 1, 2, 4, 5]
	arr2 = [9, 11, 1, 3, 6, 8, 8, 9]
	#  Get the size
	size = arr1.length
	#  Just before the Sort rotated sorted array elements
	print("Before Sort elements \n")
	task.display(arr1, size)
	# 
	# 		Before Sort
	# 		 6 , 7 , 8 , 9 , 1 , 2 , 4 , 5 
	# 		After Sort
	# 		 1, 2, 4, 5, 6, 7, 8, 9
	# 		
	
	task.sortRotatedArray(arr1, size)
	#  After modify array elements
	print("After Sort elements \n")
	task.display(arr1, size)
	#  Get the size
	size = arr2.length
	#  Just before the Sort rotated sorted array elements
	print("\nBefore Sort elements \n")
	task.display(arr2, size)
	# 
	# 		Before Sort
	# 		 9 , 11 , 1 , 3 , 6 , 8 , 8 , 9
	# 		After Sort
	# 		 1, 3, 6, 8, 8, 9, 9, 11
	# 		
	
	task.sortRotatedArray(arr2, size)
	#  After modify array elements
	print("After Sort elements \n")
	task.display(arr2, size)
end

main()

Output

Before Sort elements 
  6  7  8  9  1  2  4  5
After Sort elements 
  1  2  4  5  6  7  8  9

Before Sort elements 
  9  11  1  3  6  8  8  9
After Sort elements 
  1  3  6  8  8  9  9  11

/*
   Scala Program
   Sort a rotated sorted array
*/
class SortArray
{
    //Function which is swapping two array elements of given location
    def swapElement(arr: Array[Int], i: Int, j: Int): Unit = {
        //Get i location element
        var temp: Int = arr(i);
        //set new values
        arr(i) = arr(j);
        arr(j) = temp;
    }
    //Function which is Reversing given array elements
    def reverseElement(arr: Array[Int], a: Int, b: Int): Unit = {
        var front: Int = a;
        var tail: Int = b;
        while (front < tail)
        {
            //Swap array elements
            this.swapElement(arr, front, tail);
            front += 1;
            tail -= 1;
        }
    }
    // Handles the request to sort an given of sorted and rotated array
    def sortRotatedArray(arr: Array[Int], size: Int): Unit = {
        if (size <= 0)
        {
            return;
        }
        var i: Int = 0;
        // Find largest element in rotated array
        while (i + 1 < size && arr(i) <= arr(i + 1))
        {
            i += 1;
        }
        // When array is already sorted
        if (i >= size - 1)
        {
            return;
        }
        // Reverse the array element from index 0 to maximum element
        this.reverseElement(arr, 0, i);
        // Reverse the array element from index
        // maximum element location+1 to size-1
        this.reverseElement(arr, i + 1, size - 1);
        // Reverse entire array
        this.reverseElement(arr, 0, size - 1);
    }
    //Function which is display array elements
    def display(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 = {
        var task: SortArray = new SortArray();
        // Define the rotated sorted arrays
        var arr1: Array[Int] = Array(6, 7, 8, 9, 1, 2, 4, 5);
        var arr2: Array[Int] = Array(9, 11, 1, 3, 6, 8, 8, 9);
        // Get the size
        var size: Int = arr1.length;
        // Just before the Sort rotated sorted array elements
        print("Before Sort elements \n");
        task.display(arr1, size);
        /*
        Before Sort
        { 6 , 7 , 8 , 9 , 1 , 2 , 4 , 5 }
        After Sort
        { 1, 2, 4, 5, 6, 7, 8, 9}
        */
        task.sortRotatedArray(arr1, size);
        // After modify array elements
        print("After Sort elements \n");
        task.display(arr1, size);
        // Get the size
        size = arr2.length;
        // Just before the Sort rotated sorted array elements
        print("\nBefore Sort elements \n");
        task.display(arr2, size);
        /*
        Before Sort
        { 9 , 11 , 1 , 3 , 6 , 8 , 8 , 9}
        After Sort
        { 1, 3, 6, 8, 8, 9, 9, 11}
        */
        task.sortRotatedArray(arr2, size);
        // After modify array elements
        print("After Sort elements \n");
        task.display(arr2, size);
    }
}

Output

Before Sort elements
  6  7  8  9  1  2  4  5
After Sort elements
  1  2  4  5  6  7  8  9

Before Sort elements
  9  11  1  3  6  8  8  9
After Sort elements
  1  3  6  8  8  9  9  11
/*
   Swift 4 Program
   Sort a rotated sorted array
*/
class SortArray
{
    //Function which is swapping two array elements of given location
    func swapElement(_ arr: inout[Int], _ i: Int, _ j: Int)
    {
        //Get i location element
        let temp: Int = arr[i];
        //set new values
        arr[i] = arr[j];
        arr[j] = temp;
    }
    //Function which is Reversing given array elements
    func reverseElement(_ arr: inout[Int], _ a: Int, _ b: Int)
    {
        var front: Int = a;
        var tail: Int = b;
        while (front < tail)
        {
            //Swap array elements
            self.swapElement(&arr, front, tail);
            front += 1;
            tail -= 1;
        }
    }
    // Handles the request to sort an given of sorted and rotated array
    func sortRotatedArray(_ arr: inout[Int], _ size: Int)
    {
        if (size <= 0)
        {
            return;
        }
        var i: Int = 0;
        // Find largest element in rotated array
        while (i + 1 < size && arr[i] <= arr[i + 1])
        {
            i += 1;
        }
        // When array is already sorted
        if (i >= size - 1)
        {
            return;
        }
        // Reverse the array element from index 0 to maximum element
        self.reverseElement(&arr, 0, i);
        // Reverse the array element from index
        // maximum element location+1 to size-1
        self.reverseElement(&arr, i + 1, size - 1);
        // Reverse entire array
        self.reverseElement(&arr, 0, size - 1);
    }
    //Function which is display array elements
    func display(_ arr: [Int], _ size: Int)
    {
        var i: Int = 0;
        while (i < size)
        {
            print("  ", arr[i], terminator: "");
            i += 1;
        }
        print(terminator: "\n");
    }
}
func main()
{
    let task: SortArray = SortArray();
    // Define the rotated sorted arrays
    var arr1: [Int] = [6, 7, 8, 9, 1, 2, 4, 5];
    var arr2: [Int] = [9, 11, 1, 3, 6, 8, 8, 9];
    // Get the size
    var size: Int = arr1.count;
    // Just before the Sort rotated sorted array elements
    print("Before Sort elements ");
    task.display(arr1, size);
    /*
    Before Sort
    { 6 , 7 , 8 , 9 , 1 , 2 , 4 , 5 }
    After Sort
    { 1, 2, 4, 5, 6, 7, 8, 9}
    */
    task.sortRotatedArray(&arr1, size);
    // After modify array elements
    print("After Sort elements ");
    task.display(arr1, size);
    // Get the size
    size = arr2.count;
    // Just before the Sort rotated sorted array elements
    print("\nBefore Sort elements ");
    task.display(arr2, size);
    /*
    Before Sort
    { 9 , 11 , 1 , 3 , 6 , 8 , 8 , 9}
    After Sort
    { 1, 3, 6, 8, 8, 9, 9, 11}
    */
    task.sortRotatedArray(&arr2, size);
    // After modify array elements
    print("After Sort elements ");
    task.display(arr2, size);
}
main();

Output

Before Sort elements
   6   7   8   9   1   2   4   5
After Sort elements
   1   2   4   5   6   7   8   9

Before Sort elements
   9   11   1   3   6   8   8   9
After Sort elements
   1   3   6   8   8   9   9   11
/*
   Kotlin Program
   Sort a rotated sorted array
*/
class SortArray
{
    //Function which is swapping two array elements of given location
    fun swapElement(arr: Array<Int>, i: Int, j: Int): Unit
    {
        //Get i location element
        var temp: Int = arr[i];
        //set new values
        arr[i] = arr[j];
        arr[j] = temp;
    }
    //Function which is Reversing given array elements
    fun reverseElement(arr: Array<Int>, a: Int, b: Int): Unit
    {
        var front: Int = a;
        var tail: Int = b;
        while (front<tail)
        {
            //Swap array elements
            this.swapElement(arr, front, tail);
            front += 1;
            tail -= 1;
        }
    }
    // Handles the request to sort an given of sorted and rotated array
    fun sortRotatedArray(arr: Array<Int>, size: Int): Unit
    {
        if (size <= 0)
        {
            return;
        }
        var i: Int = 0;
        // Find largest element in rotated array
        while (i + 1<size && arr[i] <= arr[i + 1])
        {
            i += 1;
        }
        // When array is already sorted
        if (i>= size - 1)
        {
            return;
        }
        // Reverse the array element from index 0 to maximum element
        this.reverseElement(arr, 0, i);
        // Reverse the array element from index
        // maximum element location+1 to size-1
        this.reverseElement(arr, i + 1, size - 1);
        // Reverse entire array
        this.reverseElement(arr, 0, size - 1);
    }
    //Function which is display array elements
    fun display(arr: Array<Int>, size: Int): Unit
    {
        var i: Int = 0;
        while (i<size)
        {
            print("  " + arr[i]);
            i += 1;
        }
        print("\n");
    }
}
fun main(args: Array<String>): Unit
{
    var task: SortArray = SortArray();
    // Define the rotated sorted arrays
    var arr1: Array<Int> = arrayOf(6, 7, 8, 9, 1, 2, 4, 5);
    var arr2: Array<Int> = arrayOf(9, 11, 1, 3, 6, 8, 8, 9);
    // Get the size
    var size: Int = arr1.count();
    // Just before the Sort rotated sorted array elements
    print("Before Sort elements \n");
    task.display(arr1, size);
    /*
    Before Sort
    { 6 , 7 , 8 , 9 , 1 , 2 , 4 , 5 }
    After Sort
    { 1, 2, 4, 5, 6, 7, 8, 9}
    */
    task.sortRotatedArray(arr1, size);
    // After modify array elements
    print("After Sort elements \n");
    task.display(arr1, size);
    // Get the size
    size = arr2.count();
    // Just before the Sort rotated sorted array elements
    print("\nBefore Sort elements \n");
    task.display(arr2, size);
    /*
    Before Sort
    { 9 , 11 , 1 , 3 , 6 , 8 , 8 , 9}
    After Sort
    { 1, 3, 6, 8, 8, 9, 9, 11}
    */
    task.sortRotatedArray(arr2, size);
    // After modify array elements
    print("After Sort elements \n");
    task.display(arr2, size);
}

Output

Before Sort elements
  6  7  8  9  1  2  4  5
After Sort elements
  1  2  4  5  6  7  8  9

Before Sort elements
  9  11  1  3  6  8  8  9
After Sort elements
  1  3  6  8  8  9  9  11
Last updated on by Kalkicode




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.

New Comment