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