Posted on by Kalkicode
Code Algorithm

# Block swap algorithm for array rotation

The block swap algorithm is a popular method for rotating an array in-place. It works by dividing the array into two blocks, and then swapping the elements of these blocks in a specific way to achieve the desired rotation.

Let's say we have an array of length n and we want to rotate it by k positions. We first divide the array into two blocks, A and B, where A contains the first k elements of the array and B contains the remaining n-k elements.

To perform the rotation, we swap the elements of A and B in the following way:

1. Swap the first element of A with the first element of B.
2. Swap the second element of A with the second-to-last element of B.
3. Swap the third element of A with the third-to-last element of B.
4. Continue this pattern, swapping the i-th element of A with the (n-k+i)-th element of B, until we have swapped all k elements of A with their corresponding elements in B.

After performing these swaps, the array will be rotated by k positions. The time complexity of this algorithm is O(n), as we only need to perform n swaps.

It is worth noting that this algorithm only works if k is less than n. If k is greater than or equal to n, we can simply take the remainder of k when divided by n and perform the rotation using that value instead.

## Code Solution

``````// C program for
// Block swap 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");
}
// This is swapping given block elements
void swapSubArray(int arr[], int s, int e, int n)
{
// Executing the loop through by the n
for (int i = 0; i < n; i++)
{
// Swap array 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];
}
}
void blockSwapAlgo(int arr[], int n, int k)
{
if (k == 0 || k >= n)
{
// When k = 0 then result are not change
// And k >= n is greater than or equal to size n
return;
}
// Display given array
printf("\n Before rotation  ");
printf("\n Array : ");
printData(arr, n);
printf(" Given rotation k is : %d", k);
int i = k;
int j = n - k;
while (i != j)
{
if (i < j)
{
// When i is less than j
swapSubArray(arr, k - i, k + j - i, i);
// Reduce i in j
j = j - i;
}
else
{
// When j is less than i
swapSubArray(arr, k - i, k, j);
i = i - j;
}
}
swapSubArray(arr, k - i, k, i);
// Display resultant array
printf("\n After rotation  ");
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
blockSwapAlgo(arr, n, 5);
blockSwapAlgo(arr, n, 3);
return 0;
}``````

#### input

`````` Before rotation
Array :   8  7  6  5  4  3  2  1  0
Given rotation k is : 5
After rotation
Array :   3  2  1  0  8  7  6  5  4

Before rotation
Array :   3  2  1  0  8  7  6  5  4
Given rotation k is : 3
After rotation
Array :   0  8  7  6  5  4  3  2  1``````
``````/*
Java Program for
Block swap 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");
}
// This is swapping given block elements
public void swapSubArray(int[] arr, int s, int e, int n)
{
// Executing the loop through by the n
for (int i = 0; i < n; i++)
{
// Swap array 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];
}
}
public void blockSwapAlgo(int[] arr, int n, int k)
{
if (k == 0 || k >= n)
{
// When k = 0 then result are not change
// And k >= n is greater than or equal to size n
return;
}
// Display given array
System.out.println(" Before rotation ");
System.out.println(" Array : ");
printData(arr, n);
System.out.println(" Given rotation k is : " + k);
int i = k;
int j = n - k;
while (i != j)
{
if (i < j)
{
// When i is less than j
swapSubArray(arr, k - i, k + j - i, i);
// Reduce i in j
j = j - i;
}
else
{
// When j is less than i
swapSubArray(arr, k - i, k, j);
i = i - j;
}
}
swapSubArray(arr, k - i, k, i);
// Display resultant array
System.out.println(" After rotation ");
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 rotation
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotation
Array :
3 2 1 0 8 7 6 5 4

Before rotation
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotation
Array :
0 8 7 6 5 4 3 2 1
``````
``````// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Block swap 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";
}
// This is swapping given block elements
void swapSubArray(int arr[], int s, int e, int n)
{
// Executing the loop through by the n
for (int i = 0; i < n; i++)
{
// Swap array 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];
}
}
void blockSwapAlgo(int arr[], int n, int k)
{
if (k == 0 || k >= n)
{
// When k = 0 then result are not change
// And k >= n is greater than or equal to size n
return;
}
// Display given array
cout << " Before rotation " << endl;
cout << " Array : " << endl;
this->printData(arr, n);
cout << " Given rotation k is : " << k << endl;
int i = k;
int j = n - k;
while (i != j)
{
if (i < j)
{
// When i is less than j
this->swapSubArray(arr, k - i, k + j - i, i);
// Reduce i in j
j = j - i;
}
else
{
// When j is less than i
this->swapSubArray(arr, k - i, k, j);
i = i - j;
}
}
this->swapSubArray(arr, k - i, k, i);
// Display resultant array
cout << " After rotation " << 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 rotation
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotation
Array :
3 2 1 0 8 7 6 5 4

Before rotation
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotation
Array :
0 8 7 6 5 4 3 2 1
``````
``````// Include namespace system
using System;
/*
Csharp Program for
Block swap 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");
}
// This is swapping given block elements
public void swapSubArray(int[] arr, int s, int e, int n)
{
// Executing the loop through by the n
for (int i = 0; i < n; i++)
{
// Swap array 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];
}
}
public void blockSwapAlgo(int[] arr, int n, int k)
{
if (k == 0 || k >= n)
{
// When k = 0 then result are not change
// And k >= n is greater than or equal to size n
return;
}
// Display given array
Console.WriteLine(" Before rotation ");
Console.WriteLine(" Array : ");
this.printData(arr, n);
Console.WriteLine(" Given rotation k is : " + k);
int i = k;
int j = n - k;
while (i != j)
{
if (i < j)
{
// When i is less than j
this.swapSubArray(arr, k - i, k + j - i, i);
// Reduce i in j
j = j - i;
}
else
{
// When j is less than i
this.swapSubArray(arr, k - i, k, j);
i = i - j;
}
}
this.swapSubArray(arr, k - i, k, i);
// Display resultant array
Console.WriteLine(" After rotation ");
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 rotation
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotation
Array :
3 2 1 0 8 7 6 5 4

Before rotation
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotation
Array :
0 8 7 6 5 4 3 2 1
``````
``````<?php
/*
Php Program for
Block swap 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 " ".strval(\$arr[\$i]);
}
echo "\n";
}
// This is swapping given block elements
public	function swapSubArray(\$arr, \$s, \$e, \$n)
{
// Executing the loop through by the n
for (\$i = 0; \$i < \$n; \$i++)
{
// Swap array 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];
}
}
public	function blockSwapAlgo(\$arr, \$n, \$k)
{
if (\$k == 0 || \$k >= \$n)
{
// When k = 0 then result are not change
// And k >= n is greater than or equal to size n
return;
}
// Display given array
echo " Before rotation ".
"\n";
echo " Array : ".
"\n";
\$this->printData(\$arr, \$n);
echo " Given rotation k is : ".strval(\$k).
"\n";
\$i = \$k;
\$j = \$n - \$k;
while (\$i != \$j)
{
if (\$i < \$j)
{
// When i is less than j
\$this->swapSubArray(\$arr, \$k - \$i, \$k + \$j - \$i, \$i);
// Reduce i in j
\$j = \$j - \$i;
}
else
{
// When j is less than i
\$this->swapSubArray(\$arr, \$k - \$i, \$k, \$j);
\$i = \$i - \$j;
}
}
\$this->swapSubArray(\$arr, \$k - \$i, \$k, \$i);
// Display resultant array
echo " After rotation ".
"\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 rotation
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotation
Array :
8 7 6 5 4 3 2 1 0

Before rotation
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 3
After rotation
Array :
8 7 6 5 4 3 2 1 0
``````
``````/*
Node JS Program for
Block swap 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");
}
// This is swapping given block elements
swapSubArray(arr, s, e, n)
{
// Executing the loop through by the n
for (var i = 0; i < n; i++)
{
// Swap array 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];
}
}
blockSwapAlgo(arr, n, k)
{
if (k == 0 || k >= n)
{
// When k = 0 then result are not change
// And k >= n is greater than or equal to size n
return;
}
// Display given array
console.log(" Before rotation ");
console.log(" Array : ");
this.printData(arr, n);
console.log(" Given rotation k is : " + k);
var i = k;
var j = n - k;
while (i != j)
{
if (i < j)
{
// When i is less than j
this.swapSubArray(arr, k - i, k + j - i, i);
// Reduce i in j
j = j - i;
}
else
{
// When j is less than i
this.swapSubArray(arr, k - i, k, j);
i = i - j;
}
}
this.swapSubArray(arr, k - i, k, i);
// Display resultant array
console.log(" After rotation ");
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 rotation
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotation
Array :
3 2 1 0 8 7 6 5 4

Before rotation
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotation
Array :
0 8 7 6 5 4 3 2 1
``````
``````#  Python 3 Program for
#  Block swap algorithm for array rotation
class Rotation :
#  This is display the given list elements
def printData(self, arr, n) :
i = 0
#  Executing the loop through by the size of list
while (i < n) :
print(" ", arr[i], end = "")
i += 1

print(end = "\n")

#  This is swapping given block elements
def swapSubArray(self, arr, s, e, n) :
i = 0
#  Executing the loop through by the n
while (i < n) :
#  Swap list 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]
i += 1

def blockSwapAlgo(self, arr, n, k) :
if (k == 0 or k >= n) :
#  When k = 0 then result are not change
#  And k >= n is greater than or equal to size n
return

#  Display given list
print(" Before rotation ")
print(" Array : ")
self.printData(arr, n)
print(" Given rotation k is : ", k)
i = k
j = n - k
while (i != j) :
if (i < j) :
#  When i is less than j
self.swapSubArray(arr, k - i, k + j - i, i)
#  Reduce i in j
j = j - i
else :
#  When j is less than i
self.swapSubArray(arr, k - i, k, j)
i = i - j

self.swapSubArray(arr, k - i, k, i)
#  Display resultant list
print(" After rotation ")
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 rotation
Array :
8  7  6  5  4  3  2  1  0
Given rotation k is :  5
After rotation
Array :
3  2  1  0  8  7  6  5  4

Before rotation
Array :
3  2  1  0  8  7  6  5  4
Given rotation k is :  3
After rotation
Array :
0  8  7  6  5  4  3  2  1
``````
``````#  Ruby Program for
#  Block swap algorithm for array rotation
class Rotation
#  This is display the given array elements
def printData(arr, n)
i = 0
#  Executing the loop through by the size of array
while (i < n)
print(" ", arr[i])
i += 1
end

print("\n")
end

#  This is swapping given block elements
def swapSubArray(arr, s, e, n)
i = 0
#  Executing the loop through by the n
while (i < n)
#  Swap array 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]
i += 1
end

end

def blockSwapAlgo(arr, n, k)
if (k == 0 || k >= n)
#  When k = 0 then result are not change
#  And k >= n is greater than or equal to size n
return
end

#  Display given array
print(" Before rotation ", "\n")
print(" Array : ", "\n")
self.printData(arr, n)
print(" Given rotation k is : ", k, "\n")
i = k
j = n - k
while (i != j)
if (i < j)
#  When i is less than j
self.swapSubArray(arr, k - i, k + j - i, i)
#  Reduce i in j
j = j - i
else
#  When j is less than i
self.swapSubArray(arr, k - i, k, j)
i = i - j
end

end

self.swapSubArray(arr, k - i, k, i)
#  Display resultant array
print(" After rotation ", "\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 rotation
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotation
Array :
3 2 1 0 8 7 6 5 4

Before rotation
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotation
Array :
0 8 7 6 5 4 3 2 1

``````
``````/*
Scala Program for
Block swap algorithm for array rotation
*/
class Rotation()
{
// This is display the given array elements
def printData(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
// Executing the loop through by the size of array
while (i < n)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
// This is swapping given block elements
def swapSubArray(arr: Array[Int], s: Int, e: Int, n: Int): Unit = {
var i: Int = 0;
// Executing the loop through by the n
while (i < n)
{
// Swap array 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);
i += 1;
}
}
def blockSwapAlgo(arr: Array[Int], n: Int, k: Int): Unit = {
if (k == 0 || k >= n)
{
// When k = 0 then result are not change
// And k >= n is greater than or equal to size n
return;
}
// Display given array
println(" Before rotation ");
println(" Array : ");
printData(arr, n);
println(" Given rotation k is : " + k);
var i: Int = k;
var j: Int = n - k;
while (i != j)
{
if (i < j)
{
// When i is less than j
swapSubArray(arr, k - i, k + j - i, i);
// Reduce i in j
j = j - i;
}
else
{
// When j is less than i
swapSubArray(arr, k - i, k, j);
i = i - j;
}
}
swapSubArray(arr, k - i, k, i);
// Display resultant array
println(" After rotation ");
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 rotation
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotation
Array :
3 2 1 0 8 7 6 5 4

Before rotation
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotation
Array :
0 8 7 6 5 4 3 2 1
``````
``````/*
Swift 4 Program for
Block swap algorithm for array rotation
*/
class Rotation
{
// This is display the given array elements
func printData(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
// Executing the loop through by the size of array
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
// This is swapping given block elements
func swapSubArray(_ arr: inout[Int], _ s: Int, _ e: Int, _ n: Int)
{
var i: Int = 0;
// Executing the loop through by the n
while (i < n)
{
// Swap array 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];
i += 1;
}
}
func blockSwapAlgo(_ arr: inout[Int], _ n: Int, _ k: Int)
{
if (k == 0 || k >= n)
{
// When k = 0 then result are not change
// And k >= n is greater than or equal to size n
return;
}
// Display given array
print(" Before rotation ");
print(" Array : ");
self.printData(arr, n);
print(" Given rotation k is : ", k);
var i: Int = k;
var j: Int = n - k;
while (i  != j)
{
if (i < j)
{
// When i is less than j
self.swapSubArray(&arr, k - i, k + j - i, i);
// Reduce i in j
j = j - i;
}
else
{
// When j is less than i
self.swapSubArray(&arr, k - i, k, j);
i = i - j;
}
}
self.swapSubArray(&arr, k - i, k, i);
// Display resultant array
print(" After rotation ");
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 rotation
Array :
8  7  6  5  4  3  2  1  0
Given rotation k is :  5
After rotation
Array :
3  2  1  0  8  7  6  5  4

Before rotation
Array :
3  2  1  0  8  7  6  5  4
Given rotation k is :  3
After rotation
Array :
0  8  7  6  5  4  3  2  1
``````
``````/*
Kotlin Program for
Block swap 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");
}
// This is swapping given block elements
fun swapSubArray(arr: Array < Int > , s: Int, e: Int, n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
// Swap array 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];
i += 1;
}
}
fun blockSwapAlgo(arr: Array < Int > , n: Int, k: Int): Unit
{
if (k == 0 || k >= n)
{
// When k = 0 then result are not change
// And k >= n is greater than or equal to size n
return;
}
// Display given array
println(" Before rotation ");
println(" Array : ");
this.printData(arr, n);
println(" Given rotation k is : " + k.toString());
var i: Int = k;
var j: Int = n - k;
while (i != j)
{
if (i < j)
{
// When i is less than j
this.swapSubArray(arr, k - i, k + j - i, i);
// Reduce i in j
j = j - i;
}
else
{
// When j is less than i
this.swapSubArray(arr, k - i, k, j);
i = i - j;
}
}
this.swapSubArray(arr, k - i, k, i);
// Display resultant array
println(" After rotation ");
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 rotation
Array :
8 7 6 5 4 3 2 1 0
Given rotation k is : 5
After rotation
Array :
3 2 1 0 8 7 6 5 4

Before rotation
Array :
3 2 1 0 8 7 6 5 4
Given rotation k is : 3
After rotation
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