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:
Leave a Reply