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.
Example.

Arr: {0,1,2,3,4}

After block swapping

{3,4,2,1,0}

python program for Block swapping algorithm for array rotation

Algorithm

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));