# 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_{l}B_{r}changes to B_{r}B_{l}A. 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_{l}A_{r}B changes to BA_{r}A_{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 🙂

## Leave a Reply

You must be logged in to post a comment.