C++ Program for Block Swapping Algorithm

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[5] = {1, 2, 3, 4, 5} after block swapping array will be A[5] = {5, 4, 1, 2, 3}.

block swapping 09

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 fi
with 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 Code
int 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