Reversal algorithm for array rotation
The Reversal algorithm for array rotation is a simple and efficient algorithm used to rotate an array of integers by a given number of positions.
The algorithm works by reversing the order of the first d elements of the array, where d is the number of positions to rotate. It then reverses the order of the remaining elements of the array. Finally, it reverses the entire array to obtain the rotated array.
Here is the pseudocode for the Reversal algorithm for array rotation:
reverse(arr, start, end):
while start < end:
arr[start], arr[end] = arr[end], arr[start]
start += 1
end -= 1
rotateArray(arr, d):
n = len(arr)
reverse(arr, 0, d-1)
reverse(arr, d, n-1)
reverse(arr, 0, n-1)
In this algorithm, reverse() is a function that reverses the order of the elements in the given subarray arr[start:end], where start is the starting index and end is the ending index.
rotateArray() is the main function that rotates the array arr by d positions. It first computes the length of the array n, then calls reverse() on the first d elements, the next n-d elements, and finally the entire array.
The time complexity of the Reversal algorithm for array rotation is O(n), where n is the size of the input array. This algorithm is more efficient than other rotation algorithms that involve shifting elements, especially when the number of positions to rotate is large.
Here given code implementation process.
// C program for
// Reversal algorithm for array rotation
#include <stdio.h>
// This is display the given array elements
void printData(int arr[], int n)
{
// Executing the loop through by the size of array
for (int i = 0; i < n; ++i)
{
printf(" %d", arr[i]);
}
printf("\n");
}
// Reverse the array elements from s to e
void reverse(int arr[], int s, int e)
{
int i = 0;
while (i + s < e - i)
{
// Swap element
arr[s + i] = arr[s + i] + arr[e - i];
arr[e - i] = arr[s + i] - arr[e - i];
arr[s + i] = arr[s + i] - arr[e - i];
// change location
i++;
}
}
void rotateElement(int arr[], int n, int k)
{
if (k == 0)
{
return;
}
// reverse left block [0..k-1]
reverse(arr, 0, k - 1);
// reverse right block [k..n]
reverse(arr, k, n);
// reverse full array [0..n]
reverse(arr, 0, n);
}
// Handles the request of rotate array by k
void rotateArray(int arr[], int n, int k)
{
if (k <= 0)
{
// When k less than or equal to zero
return;
}
// Display given array
printf("\n Before rotate ");
printf("\n Array : ");
printData(arr, n);
printf(" Given rotation k is : %d", k);
// rotate the element
rotateElement(arr, n - 1, k % n);
// Display resultant array
printf("\n After rotate ");
printf("\n Array : ");
printData(arr, n);
}
int main(int argc, char
const *argv[])
{
// Array of integer elements
int arr[] = {
8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0
};
// Get the number of elements
int n = sizeof(arr) / sizeof(arr[0]);
// Test case
rotateArray(arr, n, 5);
rotateArray(arr, n, 3);
return 0;
}input
Before rotate
Array : 8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotate
Array : 3 2 1 0 8 7 6 5 4
Before rotate
Array : 3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotate
Array : 0 8 7 6 5 4 3 2 1/*
Java Program for
Reversal algorithm for array rotation
*/
public class Rotation
{
// This is display the given array elements
public void printData(int[] arr, int n)
{
// Executing the loop through by the size of array
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
// Reverse the array elements from s to e
public void reverse(int[] arr, int s, int e)
{
int i = 0;
while (i + s < e - i)
{
// Swap element
arr[s + i] = arr[s + i] + arr[e - i];
arr[e - i] = arr[s + i] - arr[e - i];
arr[s + i] = arr[s + i] - arr[e - i];
// change location
i++;
}
}
public void rotateElement(int[] arr, int n, int k)
{
if (k == 0)
{
return;
}
// reverse left block [0..k-1]
reverse(arr, 0, k - 1);
// reverse right block [k..n]
reverse(arr, k, n);
// reverse full array [0..n]
reverse(arr, 0, n);
}
// Handles the request of rotate array by k
public void rotateArray(int[] arr, int n, int k)
{
if (k <= 0)
{
// When k less than or equal to zero
return;
}
// Display given array
System.out.println(" Before rotate ");
System.out.println(" Array : ");
printData(arr, n);
System.out.println(" Given rotation k is : " + k);
// rotate the element
rotateElement(arr, n - 1, k % n);
// Display resultant array
System.out.println(" After rotate ");
System.out.println(" Array : ");
printData(arr, n);
System.out.print("\n");
}
public static void main(String[] args)
{
Rotation task = new Rotation();
// Array of integer elements
int[] arr = {
8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0
};
// Get the number of elements
int n = arr.length;
// Test case
task.rotateArray(arr, n, 5);
task.rotateArray(arr, n, 3);
}
}input
Before rotate
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotate
Array :
3 2 1 0 8 7 6 5 4
Before rotate
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotate
Array :
0 8 7 6 5 4 3 2 1
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Reversal algorithm for array rotation
*/
class Rotation
{
public:
// This is display the given array elements
void printData(int arr[], int n)
{
// Executing the loop through by the size of array
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
// Reverse the array elements from s to e
void reverse(int arr[], int s, int e)
{
int i = 0;
while (i + s < e - i)
{
// Swap element
arr[s + i] = arr[s + i] + arr[e - i];
arr[e - i] = arr[s + i] - arr[e - i];
arr[s + i] = arr[s + i] - arr[e - i];
// change location
i++;
}
}
void rotateElement(int arr[], int n, int k)
{
if (k == 0)
{
return;
}
// reverse left block [0..k-1]
this->reverse(arr, 0, k - 1);
// reverse right block [k..n]
this->reverse(arr, k, n);
// reverse full array [0..n]
this->reverse(arr, 0, n);
}
// Handles the request of rotate array by k
void rotateArray(int arr[], int n, int k)
{
if (k <= 0)
{
// When k less than or equal to zero
return;
}
// Display given array
cout << " Before rotate " << endl;
cout << " Array : " << endl;
this->printData(arr, n);
cout << " Given rotation k is : " << k << endl;
// rotate the element
this->rotateElement(arr, n - 1, k % n);
// Display resultant array
cout << " After rotate " << endl;
cout << " Array : " << endl;
this->printData(arr, n);
cout << "\n";
}
};
int main()
{
Rotation *task = new Rotation();
// Array of integer elements
int arr[] = {
8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0
};
// Get the number of elements
int n = sizeof(arr) / sizeof(arr[0]);
// Test case
task->rotateArray(arr, n, 5);
task->rotateArray(arr, n, 3);
return 0;
}input
Before rotate
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotate
Array :
3 2 1 0 8 7 6 5 4
Before rotate
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotate
Array :
0 8 7 6 5 4 3 2 1
// Include namespace system
using System;
/*
Csharp Program for
Reversal algorithm for array rotation
*/
public class Rotation
{
// This is display the given array elements
public void printData(int[] arr, int n)
{
// Executing the loop through by the size of array
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
// Reverse the array elements from s to e
public void reverse(int[] arr, int s, int e)
{
int i = 0;
while (i + s < e - i)
{
// Swap element
arr[s + i] = arr[s + i] + arr[e - i];
arr[e - i] = arr[s + i] - arr[e - i];
arr[s + i] = arr[s + i] - arr[e - i];
// change location
i++;
}
}
public void rotateElement(int[] arr, int n, int k)
{
if (k == 0)
{
return;
}
// reverse left block [0..k-1]
this.reverse(arr, 0, k - 1);
// reverse right block [k..n]
this.reverse(arr, k, n);
// reverse full array [0..n]
this.reverse(arr, 0, n);
}
// Handles the request of rotate array by k
public void rotateArray(int[] arr, int n, int k)
{
if (k <= 0)
{
// When k less than or equal to zero
return;
}
// Display given array
Console.WriteLine(" Before rotate ");
Console.WriteLine(" Array : ");
this.printData(arr, n);
Console.WriteLine(" Given rotation k is : " + k);
// rotate the element
this.rotateElement(arr, n - 1, k % n);
// Display resultant array
Console.WriteLine(" After rotate ");
Console.WriteLine(" Array : ");
this.printData(arr, n);
Console.Write("\n");
}
public static void Main(String[] args)
{
Rotation task = new Rotation();
// Array of integer elements
int[] arr = {
8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0
};
// Get the number of elements
int n = arr.Length;
// Test case
task.rotateArray(arr, n, 5);
task.rotateArray(arr, n, 3);
}
}input
Before rotate
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotate
Array :
3 2 1 0 8 7 6 5 4
Before rotate
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotate
Array :
0 8 7 6 5 4 3 2 1
<?php
/*
Php Program for
Reversal algorithm for array rotation
*/
class Rotation
{
// This is display the given array elements
public function printData($arr, $n)
{
// Executing the loop through by the size of array
for ($i = 0; $i < $n; ++$i)
{
echo(" ".$arr[$i]);
}
echo("\n");
}
// Reverse the array elements from s to e
public function reverse(&$arr, $s, $e)
{
$i = 0;
while ($i + $s < $e - $i)
{
// Swap element
$arr[$s + $i] = $arr[$s + $i] + $arr[$e - $i];
$arr[$e - $i] = $arr[$s + $i] - $arr[$e - $i];
$arr[$s + $i] = $arr[$s + $i] - $arr[$e - $i];
// change location
$i++;
}
}
public function rotateElement(&$arr, $n, $k)
{
if ($k == 0)
{
return;
}
// reverse left block [0..k-1]
$this->reverse($arr, 0, $k - 1);
// reverse right block [k..n]
$this->reverse($arr, $k, $n);
// reverse full array [0..n]
$this->reverse($arr, 0, $n);
}
// Handles the request of rotate array by k
public function rotateArray(&$arr, $n, $k)
{
if ($k <= 0)
{
// When k less than or equal to zero
return;
}
// Display given array
echo(" Before rotate \n");
echo(" Array : \n");
$this->printData($arr, $n);
echo(" Given rotation k is : ".$k.
"\n");
// rotate the element
$this->rotateElement($arr, $n - 1, $k % $n);
// Display resultant array
echo(" After rotate \n");
echo(" Array : \n");
$this->printData($arr, $n);
echo("\n");
}
}
function main()
{
$task = new Rotation();
// Array of integer elements
$arr = array(8, 7, 6, 5, 4, 3, 2, 1, 0);
// Get the number of elements
$n = count($arr);
// Test case
$task->rotateArray($arr, $n, 5);
$task->rotateArray($arr, $n, 3);
}
main();input
Before rotate
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotate
Array :
3 2 1 0 8 7 6 5 4
Before rotate
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotate
Array :
0 8 7 6 5 4 3 2 1
/*
Node JS Program for
Reversal algorithm for array rotation
*/
class Rotation
{
// This is display the given array elements
printData(arr, n)
{
// Executing the loop through by the size of array
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
// Reverse the array elements from s to e
reverse(arr, s, e)
{
var i = 0;
while (i + s < e - i)
{
// Swap element
arr[s + i] = arr[s + i] + arr[e - i];
arr[e - i] = arr[s + i] - arr[e - i];
arr[s + i] = arr[s + i] - arr[e - i];
// change location
i++;
}
}
rotateElement(arr, n, k)
{
if (k == 0)
{
return;
}
// reverse left block [0..k-1]
this.reverse(arr, 0, k - 1);
// reverse right block [k..n]
this.reverse(arr, k, n);
// reverse full array [0..n]
this.reverse(arr, 0, n);
}
// Handles the request of rotate array by k
rotateArray(arr, n, k)
{
if (k <= 0)
{
// When k less than or equal to zero
return;
}
// Display given array
console.log(" Before rotate ");
console.log(" Array : ");
this.printData(arr, n);
console.log(" Given rotation k is : " + k);
// rotate the element
this.rotateElement(arr, n - 1, k % n);
// Display resultant array
console.log(" After rotate ");
console.log(" Array : ");
this.printData(arr, n);
process.stdout.write("\n");
}
}
function main()
{
var task = new Rotation();
// Array of integer elements
var arr = [8, 7, 6, 5, 4, 3, 2, 1, 0];
// Get the number of elements
var n = arr.length;
// Test case
task.rotateArray(arr, n, 5);
task.rotateArray(arr, n, 3);
}
main();input
Before rotate
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotate
Array :
3 2 1 0 8 7 6 5 4
Before rotate
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotate
Array :
0 8 7 6 5 4 3 2 1
# Python 3 Program for
# Reversal algorithm for array rotation
class Rotation :
# This is display the given list elements
def printData(self, arr, n) :
# Executing the loop through by the size of list
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1
print(end = "\n")
# Reverse the list elements from s to e
def reverse(self, arr, s, e) :
i = 0
while (i + s < e - i) :
# Swap element
arr[s + i] = arr[s + i] + arr[e - i]
arr[e - i] = arr[s + i] - arr[e - i]
arr[s + i] = arr[s + i] - arr[e - i]
# change location
i += 1
def rotateElement(self, arr, n, k) :
if (k == 0) :
return
# reverse left block [0..k-1]
self.reverse(arr, 0, k - 1)
# reverse right block [k..n]
self.reverse(arr, k, n)
# reverse full list [0..n]
self.reverse(arr, 0, n)
# Handles the request of rotate list by k
def rotateArray(self, arr, n, k) :
if (k <= 0) :
# When k less than or equal to zero
return
# Display given list
print(" Before rotate ")
print(" Array : ")
self.printData(arr, n)
print(" Given rotation k is : ", k)
# rotate the element
self.rotateElement(arr, n - 1, k % n)
# Display resultant list
print(" After rotate ")
print(" Array : ")
self.printData(arr, n)
print(end = "\n")
def main() :
task = Rotation()
arr = [8, 7, 6, 5, 4, 3, 2, 1, 0]
n = len(arr)
# Test case
task.rotateArray(arr, n, 5)
task.rotateArray(arr, n, 3)
if __name__ == "__main__": main()input
Before rotate
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotate
Array :
3 2 1 0 8 7 6 5 4
Before rotate
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotate
Array :
0 8 7 6 5 4 3 2 1
# Ruby Program for
# Reversal algorithm for array rotation
class Rotation
# This is display the given array elements
def printData(arr, n)
# Executing the loop through by the size of array
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end
print("\n")
end
# Reverse the array elements from s to e
def reverse(arr, s, e)
i = 0
while (i + s < e - i)
# Swap element
arr[s + i] = arr[s + i] + arr[e - i]
arr[e - i] = arr[s + i] - arr[e - i]
arr[s + i] = arr[s + i] - arr[e - i]
# change location
i += 1
end
end
def rotateElement(arr, n, k)
if (k == 0)
return
end
# reverse left block [0..k-1]
self.reverse(arr, 0, k - 1)
# reverse right block [k..n]
self.reverse(arr, k, n)
# reverse full array [0..n]
self.reverse(arr, 0, n)
end
# Handles the request of rotate array by k
def rotateArray(arr, n, k)
if (k <= 0)
# When k less than or equal to zero
return
end
# Display given array
print(" Before rotate ", "\n")
print(" Array : ", "\n")
self.printData(arr, n)
print(" Given rotation k is : ", k, "\n")
# rotate the element
self.rotateElement(arr, n - 1, k % n)
# Display resultant array
print(" After rotate ", "\n")
print(" Array : ", "\n")
self.printData(arr, n)
print("\n")
end
end
def main()
task = Rotation.new()
# Array of integer elements
arr = [8, 7, 6, 5, 4, 3, 2, 1, 0]
# Get the number of elements
n = arr.length
# Test case
task.rotateArray(arr, n, 5)
task.rotateArray(arr, n, 3)
end
main()input
Before rotate
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotate
Array :
3 2 1 0 8 7 6 5 4
Before rotate
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotate
Array :
0 8 7 6 5 4 3 2 1
/*
Scala Program for
Reversal algorithm for array rotation
*/
class Rotation()
{
// This is display the given array elements
def printData(arr: Array[Int], n: Int): Unit = {
// Executing the loop through by the size of array
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
// Reverse the array elements from s to e
def reverse(arr: Array[Int], s: Int, e: Int): Unit = {
var i: Int = 0;
while (i + s < e - i)
{
// Swap element
arr(s + i) = arr(s + i) + arr(e - i);
arr(e - i) = arr(s + i) - arr(e - i);
arr(s + i) = arr(s + i) - arr(e - i);
// change location
i += 1;
}
}
def rotateElement(arr: Array[Int], n: Int, k: Int): Unit = {
if (k == 0)
{
return;
}
// reverse left block [0..k-1]
reverse(arr, 0, k - 1);
// reverse right block [k..n]
reverse(arr, k, n);
// reverse full array [0..n]
reverse(arr, 0, n);
}
// Handles the request of rotate array by k
def rotateArray(arr: Array[Int], n: Int, k: Int): Unit = {
if (k <= 0)
{
// When k less than or equal to zero
return;
}
// Display given array
println(" Before rotate ");
println(" Array : ");
printData(arr, n);
println(" Given rotation k is : " + k);
// rotate the element
rotateElement(arr, n - 1, k % n);
// Display resultant array
println(" After rotate ");
println(" Array : ");
printData(arr, n);
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Rotation = new Rotation();
// Array of integer elements
var arr: Array[Int] = Array(8, 7, 6, 5, 4, 3, 2, 1, 0);
// Get the number of elements
var n: Int = arr.length;
// Test case
task.rotateArray(arr, n, 5);
task.rotateArray(arr, n, 3);
}
}input
Before rotate
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotate
Array :
3 2 1 0 8 7 6 5 4
Before rotate
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotate
Array :
0 8 7 6 5 4 3 2 1
/*
Swift 4 Program for
Reversal algorithm for array rotation
*/
class Rotation
{
// This is display the given array elements
func printData(_ arr: [Int], _ n: Int)
{
// Executing the loop through by the size of array
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
// Reverse the array elements from s to e
func reverse(_ arr: inout[Int], _ s: Int, _ e: Int)
{
var i: Int = 0;
while (i + s < e - i)
{
// Swap element
arr[s + i] = arr[s + i] + arr[e - i];
arr[e - i] = arr[s + i] - arr[e - i];
arr[s + i] = arr[s + i] - arr[e - i];
// change location
i += 1;
}
}
func rotateElement(_ arr: inout[Int], _ n: Int, _ k: Int)
{
if (k == 0)
{
return;
}
// reverse left block [0..k-1]
self.reverse(&arr, 0, k - 1);
// reverse right block [k..n]
self.reverse(&arr, k, n);
// reverse full array [0..n]
self.reverse(&arr, 0, n);
}
// Handles the request of rotate array by k
func rotateArray(_ arr: inout[Int], _ n: Int, _ k: Int)
{
if (k <= 0)
{
// When k less than or equal to zero
return;
}
// Display given array
print(" Before rotate ");
print(" Array : ");
self.printData(arr, n);
print(" Given rotation k is : ", k);
// rotate the element
self.rotateElement(&arr, n - 1, k % n);
// Display resultant array
print(" After rotate ");
print(" Array : ");
self.printData(arr, n);
print(terminator: "\n");
}
}
func main()
{
let task: Rotation = Rotation();
// Array of integer elements
var arr: [Int] = [8, 7, 6, 5, 4, 3, 2, 1, 0];
// Get the number of elements
let n: Int = arr.count;
// Test case
task.rotateArray(&arr, n, 5);
task.rotateArray(&arr, n, 3);
}
main();input
Before rotate
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotate
Array :
3 2 1 0 8 7 6 5 4
Before rotate
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotate
Array :
0 8 7 6 5 4 3 2 1
/*
Kotlin Program for
Reversal algorithm for array rotation
*/
class Rotation
{
// This is display the given array elements
fun printData(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(" " + arr[i].toString());
i += 1;
}
print("\n");
}
// Reverse the array elements from s to e
fun reverse(arr: Array < Int > , s: Int, e: Int): Unit
{
var i: Int = 0;
while (i + s < e - i)
{
// Swap element
arr[s + i] = arr[s + i] + arr[e - i];
arr[e - i] = arr[s + i] - arr[e - i];
arr[s + i] = arr[s + i] - arr[e - i];
// change location
i += 1;
}
}
fun rotateElement(arr: Array < Int > , n: Int, k: Int): Unit
{
if (k == 0)
{
return;
}
// reverse left block [0..k-1]
this.reverse(arr, 0, k - 1);
// reverse right block [k..n]
this.reverse(arr, k, n);
// reverse full array [0..n]
this.reverse(arr, 0, n);
}
// Handles the request of rotate array by k
fun rotateArray(arr: Array < Int > , n: Int, k: Int): Unit
{
if (k <= 0)
{
// When k less than or equal to zero
return;
}
// Display given array
println(" Before rotate ");
println(" Array : ");
this.printData(arr, n);
println(" Given rotation k is : " + k.toString());
// rotate the element
this.rotateElement(arr, n - 1, k % n);
// Display resultant array
println(" After rotate ");
println(" Array : ");
this.printData(arr, n);
print("\n");
}
}
fun main(args: Array < String > ): Unit
{
val task: Rotation = Rotation();
// Array of integer elements
val arr: Array < Int > = arrayOf(8, 7, 6, 5, 4, 3, 2, 1, 0);
// Get the number of elements
val n: Int = arr.count();
// Test case
task.rotateArray(arr, n, 5);
task.rotateArray(arr, n, 3);
}input
Before rotate
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotate
Array :
3 2 1 0 8 7 6 5 4
Before rotate
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotate
Array :
0 8 7 6 5 4 3 2 1
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