Video courses for company/skill based Preparation
Purchase mock tests for company/skill building
Python program for Block swapping algorithm for array rotation
Block swap algorithm for array rotation
Here in this program we will be learning about Block swap algorithm. It is one of the most efficient algorithms used for array rotation. Now, let’s discuss about block swap algorithm and a program to rotate an array using the same algorithm.
After block swapping
The algorithm to rotate an array using block swapping algorithm are:-
Step 1- Initialize array A and B and then split them
Step 2 -A = arr[0….d-1] and B = arr[d….size-1] // d = no_of_rotations
Step 3-Repeat until size of A = size of B.
a- If A is shorter:
b- Divide B into Bl and Br such that Br is of same length as A. // Bl = B’s left block, Br = B’s right block
Step 4- Swap A and Br to change ABlBr into BrBlA.
Step 5- Now A is at its final place. Recur on pieces of B.
Step 6-If A is longer:
a- Divide A into Al and Ar such that Al is of same length as B. // Al = A’s left block, Ar = A’s right block
b- Swap Al and B to change AlArB into BArAl.
Step 7- Now B is at its final place. Recur on pieces of A.
Python program –
def leftRotate(arr, d, n): leftRotateRec(arr, 0, d, n); def leftRotateRec(arr, i, d, n): if (d == 0 or d == n): return; if (n - d == d): swap(arr, i, n - d + i, d); return; if (d < n - d): swap(arr, i, n - d + i, d); leftRotateRec(arr, i, d, n - d); else: swap(arr, i, d, n - d); leftRotateRec(arr, n - d + i, 2 * d - n, d); def printArray(arr, size): for i in range(size): print(arr[i], end = " "); print(); def swap(arr, fi, si, d): for i in range(d): temp = arr[fi + i]; arr[fi + i] = arr[si + i]; arr[si + i] = temp; arr = list(map(int,input("ENTER ARRAY ELEMENTS ").split())) no_of_rotations=2 leftRotate(arr, no_of_rotations, len(arr)); printArray(arr, len(arr));