 # Block swap algorithm for array rotation

Block swap algorithm is one of the efficient algorithms used for array rotation. Now, let us see about block swap algorithm and a program to rotate an array using the same algorithm.

## Block Swap Algorithm

• The algorithm to rotate an array using block swapping algorithm is as follows:
• Split the input array and initialize arrays A and B as:
A = arr[0….d-1] and B = arr[d….size-1]     //   d = no_of_rotations
• Repeat until size of A = size of B.
• If A is shorter:
• Divide B into Bl and Br such that Br is of same length as A.   //    Bl = B's left block, Br = B's right block
• Swap A and Br to change ABlBr into BrBlA.
• Now A is at its final place. Recur on pieces of B.
• If A is longer:
• Divide A into Al and Ar such that Al is of same length as B.   //   Al = A's left block, Ar = A's right block
• Swap Al and B to change AlArB into BArAl.
• Now B is at its final place. Recur on pieces of A.
• Finally when A and B are of equal size, block swap them.

## C++ program to rotate an array using block swap algorithm

`#include <bits/stdc++.h>using namespace std;/* swaps d elements starting at index awith d elements starting at index b */void swap(int arr[], int a, int b, int d){int i, temp;for(i = 0; i < d; i++){temp = arr[a + i];arr[a + i] = arr[b + i];arr[b + i] = temp;}}void array_left_rotate(int arr[], int d, int n){int i, j;if(d == 0 || d == n) // Return the array when no_of_rotations = 0 or nreturn;i = d;j = n - d;while (i != j){if(i < j) /*A is shorter*/{swap(arr, d-i, d+j-i, i);j = j - i;}else /*B is shorter*/{swap(arr, d-i, d, j);i = i - j;}}/*Finally, block swap A and B*/swap(arr, d-i, d, i);} int main(){int arr[] = { 1, 2, 3, 4, 5, 6, 7};int n = sizeof(arr) / sizeof(arr); // Finding the size of the arraycout<<"\nArray elements before rotating : \n";for(int i = 0; i < n; i++){cout<<arr[i]<<"\t"; // Printing the array elements}int no_of_rotations = 1; // Number of rotations to take placearray_left_rotate(arr, no_of_rotations, n);cout<<"\n\nArray elements after rotating : \n";for(int i = 0; i < n; i++){cout<<arr[i]<<"\t"; // Printing the array elements after rotation of elements}cout<<"\n";return 0;}`

OUTPUT ## Java program to rotate an array using block swap algorithm

`import java.util.Arrays; public class Main{ /* swaps d elements starting at index awith d elements starting at index b */public static void swap(int arr[], int a, int b, int d) { int i, temp; for(i = 0 ; i < d ; i++) { temp = arr[a + i]; arr[a + i] = arr[b + i]; arr[b + i] = temp; } }public static void leftRotate(int arr[], int d, int n) { int i, j; if(d == 0 || d == n) return; i = d; j = n - d; while (i != j) { if(i < j) /*A is shorter*/{ swap(arr, d-i, d+j-i, i); j = j - i; } else /*B is shorter*/{ swap(arr, d-i, d, j); i = i - j; } }/*Finally, block swap A and B*/swap(arr, d-i, d, i); } /* Main Function */public static void main(String[] args) { int arr[] = new int[]{1, 2, 3, 4, 5, 6,7}; int n = arr.length;int no_of_rotations = 2;System.out.println("Array Elements before rotating : "); for(int i = 0 ; i < n ; i++){System.out.print(arr[i]+ " "); // Printing elements before rotation}leftRotate(arr, no_of_rotations, n); System.out.println("\nArray Elements after rotating : "); for(int i = 0 ; i < n ; i++){System.out.print(arr[i] + " "); // Printing elements after rotation}}}`

## Python program to rotate an array using block swap algorithm

`/* swaps d elements starting at index awith d elements starting at index b */def swap(arr, a, b, d):   for i in range(0,d):   temp = arr[a + i];    arr[a + i] = arr[b + i];    arr[b + i] = temp; def leftRotate(arr, d, n):  if(d == 0 or d == n):  return; i = d j = n - d while (i != j):  if(i < j): # A is shorter  swap(arr, d - i, d + j - i, i)  j -= i  else: # B is shorter  swap(arr, d - i, d, j)  i -= j  swap(arr, d - i, d, i) # Main Function import array as arrarr = arr.array('i', [1,2,3,4,5,6,7]) print ("The new created array is : ") n = len(arr)no_of_rotations = 2print("Array Elements before rotation : ") for i in range (0, n):  print (arr[i], end = ' ')  # printing original array  leftRotate(arr, no_of_rotations, n )print("\nArray Elements after rotation : ") for i in range (0, n):  print (arr[i], end = ' ')  # printing array after rotation `

### Relevant exercises

POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

`2    3`

`5`
`5`
`5`