Posted on by Kalkicode
Code Algorithm

# 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)
{
// 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
}
}``````

#### 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()
{
// 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
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)
{
// 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
}
}``````

#### 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()
{
// 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
}
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()
{
// 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
}
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() :
arr = [8, 7, 6, 5, 4, 3, 2, 1, 0]
n = len(arr)
#  Test case

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()
#  Array of integer elements
arr = [8, 7, 6, 5, 4, 3, 2, 1, 0]
#  Get the number of elements
n = arr.length
#  Test case
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
}
}``````

#### 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()
{
// 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
}
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
{
// 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
}``````

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

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post