Block swap algorithm for rotation of the array

By Manisha Rathore

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:

Leave a Reply