# Block Swapping Algorithm for array rotation

Block swap algorithm is one of the efficient algorithm used for array rotation.

Now , let’s understand it with an example A = {1, 2, 3, 4, 5} after block swapping array will be A = {5, 4, 1, 2, 3}. ## Algorithm :

• Initialize the array arr[ ] and then split them into two array A and B.
• A[ ] = arr[0…p-1] and B[ ] = arr[p….size-1] , p denotes the number of rotations.
• Repeats until size of array A = size of array B.
• If A[ ] is shorter, Divide array B into two array say BL[ ] and BR[ ], in which size of BL array is same as size of array A[ ] . Here BL[ ] = left part of B[ ] and BR[ ] = right part of B[ ].
• Swap  A[ ] with BR[ ], Now A[ ] is at its final place.
• Recur on B[ ].
• If A[ ] is longer then,
• Divide A[ ] into two arrays AL[ ] and AR[ ].
• Swap  B[ ] with AL[ ], Now B[ ] is at its final place.
• Recur on A[ ].

## C++ Program based on above algorithm:

`#include <bits/stdc++.h>using namespace std;/*Prototype for swap functions */void swap(int arr[], int fi, int si, int d);void Rotate(int arr[], int p, int n){    /* Return If number of elements to be rotated     is zero or equal to array size */    if(p == 0 || p == n)        return;    /*If number of elements to be rotated    is exactly half of array size */    if(n - p == p)    {        swap(arr, 0, n - p, p);        return;    }    /* If A is shorter*/           if(p < n - p)    {        swap(arr, 0, n - p, p);        Rotate(arr, p, n - p);        }    else /* If B is shorter*/           {        swap(arr, 0, p, n - p);        Rotate(arr + n - p, 2 * p - n, p);     }}/*This function swaps d elements starting at index fiwith p elements starting at index si */void swap(int arr[], int fi, int si, int p){    int i, temp;    for(i = 0; i < p; i++)    {        temp = arr[fi + i];        arr[fi + i] = arr[si + i];        arr[si + i] = temp;    }}// Driver Codeint main(){    int arr[] = {1, 2, 3, 4, 5, 6, 7,8};    Rotate(arr, 2, 8);    for(int i=0; i<8; i++)    cout<<arr[i]<<" ";    return 0;}`

## Output :

`3 4 5 6 7 8 1 2`