# Block Swap Algorithm for Array Rotation

Learn about the block swap algorithm for array rotation and its implementation using C++ programs.
Submitted by Vikneshwar GK, on February 14, 2022

Array Rotation

Consider an integer array of size n and an integer d. The task at hand is to rotate the elements anti-clockwise by d elements, i.e., place the first d elements at the end of the array by pushing the remaining elements to the front.

Example:

```Input:
array[]= {1, 2, 3, 4, 5}
d = 3

Output:
array[] = {4, 5, 1, 2, 3}

Input:
array[]= {10, 20, 30, 40, 50}
d = 1

Output: array[]= {20, 30, 40, 50, 10}
```

## Block Swap Algorithm

This algorithm involves the array to be split into blocks and working on them individually to get the desired result. It involves the following steps:

• Split the into two groups, G1 = array[0..d-1] and G2 = array[d..n-1]
• If the length of G1 is lesser than G2, then split G2 into two groups, G2L and G2R, in such a way that the size of G1 is the same as G2R. Swap G1 and G2R. The order of array will look like, G2R, G2L, G1.
• If the length of G1 is greater than G2, then split G1 into two groups, G1L and G1R, in such a way that the size of G2 is the same as G1L. Swap G2 and G1L. The order of array will look like, G2, G1R, G1L.
• Repeat the above steps until the size of G1 is equal to G2
• Print the array

Solution 1: Using Recursion

## C++ Implementation

```#include <bits/stdc++.h>
using namespace std;

// function declaration
void swap(int array[], int group1, int, int d);

// Function to rotate array
// using block swap
void rotate(int array[], int d, int length)
{
// null check
if (d == 0 || d == length)
return;

// case to handle when d greater than length
if (d > length)
d = d % length;

// if two groups size are equal
// swap once
if (length - d == d) {
swap(array, 0, length - d, d);
return;
}

// group 1 is shorter
if (d < length - d) {
swap(array, 0, length - d, d);
rotate(array, d, length - d);
}
// group 2 is shorter
else {
swap(array, 0, d, length - d);
rotate(array + length - d, 2 * d - length, d);
}
}

// function to swap the array
void swap(int array[], int group1, int group2, int d)
{
int i, temp;
for (i = 0; i < d; i++) {
temp = array[group1 + i];
array[group1 + i] = array[group2 + i];
array[group2 + i] = temp;
}
}

//Function to print the array
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
cout << array[i] << " ";
cout << endl;
}

// Main function
int main()
{
int array[100], N, d;

cout << "Enter Number of elements: ";
cin >> N;

for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}
cout << "Enter the value of d: ";
cin >> d;

rotate(array, d, N);
cout << "Rotated Array" << endl;
printArray(array, N);

return 0;
}
```

Output:

```Enter Number of elements: 6
Enter element 1:2
Enter element 2:4
Enter element 3:6
Enter element 4:8
Enter element 5:10
Enter element 6:12
Enter the value of d: 3
Rotated Array
8 10 12 2 4 6
```

Solution 2: Using while-loop

## C++ Implementation

```#include <bits/stdc++.h>
using namespace std;

// function declaration
void swap(int array[], int group1, int, int d);

// Function to rotate array
// using block swap
void rotate(int array[], int d, int length)
{
int i, j;

// null check
if (d == 0 || d == length)
return;

// case to handle when d greater than length
if (d > length)
d = d % length;

i = d;
j = length - d;

while (i != j) {
// group 1 is shorter
if (i < j) {
swap(array, d - i, d + j - i, i);
j -= i;
}
// group 2 is shorter
else {
swap(array, d - i, d, j);
i -= j;
}
}
swap(array, d - i, d, i);
}

// function to swap the array
void swap(int array[], int group1, int group2, int d)
{
int i, temp;
for (i = 0; i < d; i++) {
temp = array[group1 + i];
array[group1 + i] = array[group2 + i];
array[group2 + i] = temp;
}
}

// Function to print the array
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
cout << array[i] << " ";
cout << endl;
}

// Main function
int main()
{
int array[100], N, d;

cout << "Enter Number of elements: ";
cin >> N;

for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}
cout << "Enter the value of d: ";
cin >> d;

rotate(array, d, N);
cout << "Rotated Array" << endl;
printArray(array, N);

return 0;
}
```

Output:

```Enter Number of elements: 5
Enter element 1:5
Enter element 2:4
Enter element 3:3
Enter element 4:2
Enter element 5:1
Enter the value of d: 2
Rotated Array
3 2 1 5 4
```

Time Complexity: O(n), where n is the length of the array.