Block swap algorithm for rotation of the array

In this tutorial, we will learn about the block-swap algorithm for rotation of the array in C++. Also, we will have an array and we have to rotate the array by s elements.

For Example:

• Given array: {4, 5, 12, 8, 1, 9}
• Here s=2
• Rotate elements by 2 in the array.
• The output: { 12, 8, 1, 9, 4, 5 }

Approach:

• Firstly, initialize the array x and y.
• Go for the following steps until the size of the array x becomes equal to the size of the array.
• If x is shorter than y, then divide y into yl and yr such that yr is of the length equal to x. Now, Swap x and yr to change xylyr into yrylx. Now x is at the final position, so we will recur on y pieces.
• If y is shorter than x, then divide x into xl and xr such that xl is of the length equal to y. Now, Swap xl and y to change xlxry into yxrxl. Now y is at the final position, so we will recur on x pieces.
• Finally, the size of the array x is equal to the size of the array y. Now, Block swap them. This is the block swap algorithm.

You may also like:
How to Validate a phone number in C++?

C++ program of Block-swap algorithm for rotation of the array

Hence, you can see the recursive implementation here.

#include<iostream>

using namespace std;
void printarr(int arr[], int sz);
void swapfn(int arr[], int ff, int ss, int s);

void lftrotation(int arr[], int s, int no)
{
// If number of elements that is rotated equal to zero or if equal to size of the array
if(s == 0 || s == no)
return;

if(no-s == s)
{
swapfn(arr, 0, no-s, s);
return;
}

/* If x is short*/
if(s< no-s)
{
swapfn(arr, 0, no-s, s);
lftrotation(arr, s, no-s);
}
else /* If y is short than x*/
{
swapfn(arr, 0, s, no-s);
lftrotation(arr+no-s, 2*s-no, s);
}
}
// print
void printarr(int arr[], int sz)
{
int i;
for(i = 0; i < sz; i++)
cout<<arr[i];
}

void swapfn(int arr[], int ff, int ss, int s)
{
int tmp;
for(int i = 0; i<s; i++)
{
tmp = arr[ff + i];
arr[ff + i] = arr[ss + i];
arr[ss + i] = tmp;
}
}

int main()
{
int arr[] = {4,1,8,0,5,6};
lftrotation(arr, 2, 6);
printarr(arr, 7);
getchar();
return 0;
}

OUTPUT EXPLANATION:

INPUT: {4,1,8,0,5,6}
s=2
OUTPUT: {8,0,5,6,4,1}

You may also read: