Block swap algorithm for array rotation in Python

Block swap algorithm for array rotation is used to swap two non-overlapping regions of an array of equal size. It is one of the efficient algorithms for array rotation.

Input: arr = [1,2,3,4,5]
       no. of rotations : 2
Output: [3,4,5,1,2]

Input: arr = [1,2,3,4,5,6]
       no. of rotations : 3
Output: [4,5,6,1,2,3]

Algorithm

Initialize arrays A and B such that A = arr[0..d-1] and B = arr[d..n-1]  where d is the no. of rotations and n is the length of the array.

Until the length of array A becomes equal to the length of B, do the following steps:

• If A is shorter, we divide B into B_l and B_r such that the length of B_r equals the length as A. Swap A and B_r such that AB_lB_r changes to B_rB_lA. Repeat the same on pieces of B.
• If A is longer, we divide A into A_l and A_r such that the length of A_l equals the length as B. Swap A_l and B such that A_lA_rB changes to BA_rA_l. Repeat the same on pieces of A.

When the size of A and B become equal, swap them.

Implementation Example:

arr = [1,2,3,4,5,6,7]
No. of rotations = 2

=> A = [1,2] and B = [3,4,5,6,7]
len(A)<len(B) => Bl = [3,4,5] and Br = [6,7]
Swap A and Br => [6,7], [3,4,5], [1,2] => [6,7,3,4,5], [1,2] and apply on [6,7,3,4,5]
=> A = [6,7] and B = [3,4,5] => Bl = [3] and Br = [4,5]
Swap A and Br => [4,5,3], [6,7] and apply on [4,5,3]
=> A = [4,5] and B = [3] => Al = [4] and Ar = [5]
Swap Al and B => [3], [5,4] and apply on [5,4]
=> A = [5] and B = [4] and len(A)=len(B)
Swap => [4,5]

Output: [3,4,5,6,7,1,2]

Python program for block Swap Algorithm for Array Rotation

Below is the Python code of the implementation of the block Swap Algorithm for Array Rotation:

def swap(arr, a, b, d):
    for i in range(0,d):
        temp = arr[a + i]
        arr[a + i] = arr[b + i]
        arr[b + i] = temp

def leftRotate(arr, d, n): 
    if(d == 0 or d == n): 
        return
    i = d 
    j = n - d 
    while (i != j): 
        if(i < j): # A is shorter 
            swap(arr, d - i, d + j-i, i) 
            j -= i 
        else: # B is shorter 
            swap(arr, d - i, d, j) 
            i -= j 
    swap(arr, d - i, d, i) #final blockswap for i=j case


import array as arr
n = int(input("Enter the length of the array: "))
a = arr.array('i', []) 
print("Enter the elements: ")
for i in range(int(n)):
    e = int(input())
    a.append(e)
rot = int(input("Enter no. of rotations: "))

print("Array Elements before rotation : ") 
for i in range (0, n): 
    print (a[i], end = ' ')

leftRotate(a, rot, n )
print("\nArray Elements after rotation : ") 
for i in range (0, n): 
    print (a[i], end = ' ')

After running the above code, below is our result:

Enter the length of the array: 7
Enter the elements:
1 2 3 4 5 6 7
Enter no. of rotations: 3
Array Elements before rotation :
1 2 3 4 5 6 7
Array Elements after rotation :
4 5 6 7 1 2 3

I am Vamsi Krishna and you can read all my posts here

Also Read: Floyd Warshall Algorithm in Python

Thank You for Reading and Keep Learning 🙂