Block Swap Algorithm for Array Rotation

Introduction

Hi all, let’s learn today about how to perform Array Rotation. There are various approaches for the same, like the brute force method, the Juggling Algorithm, the Reversal Algorithm, the Block Swap Algorithm, etc. 

In detail, let’s discuss one of the most optimized approaches for the Array Rotation, i.e. Block Swap Algorithm for Array Rotation.   

Problem Statement:  We are given an array of elements and r, i.e., a number by which we need to rotate the array and return the final rotated array.

Block Swap Algorithm for Array Rotation is a prevalent and renowned approach for the same.

In this, 

1. We divide the given array into two subarrays A and B, where A stores first ‘r’ elements and B stores the following ‘n-r’ elements. 

Where  n = size of elements in array

r = number of rotations

2. If both subarrays’ size is not equal, perform a block swap between A and B, where the block size is the size of the smaller subarray. Reduce the size of the larger subarray by the block size. 

• If Block A’s size is smaller than the size of Block B, divide the block B into two parts Bl and Br, where Br is the same size as that of A, perform a block swap between A and Br and the array changes from ABlBr to BrBlA. This places the elements of the smaller block i.e A to their correct rotated positions(After k rotations)
• If Block B’s size is smaller than the size of Block A, divide the block A into two parts Al and Ar, where Al is the same size as that of B, perform a block swap between Al and B and the array changes from AlArB to BArAl. This places the elements of the smaller block i.e B to their correct rotated positions(After k rotations)

Repeat until both the subarrays are of equal size.

3. At last perform block swap between A and B.

Let’s follow through an example:

Suppose we are given arr = [1,2,3,4,5] r = 2

Step1: We divide the entire array into two parts: r and n-r. So, subarray A would have 2 elements, and array B would have n-r  = 5-2 = 3 elements.

Step2: Compare the size of both the subarrays A and B. 

Step3: Since A’s size < B’s size. So, divide B subarray into other 2 parts – Bl and Br. 

Br is the same size as subarray A from the end, and Bl is the remaining length. 

Step4: Swap elements of subarray A and Br. 

So, ABlBr array changes to BrBlA in terms of elements, and A subarray elements come at their final position.

Step5: Now, we again compare the size of the remaining non-final subarrays, i.e., A and B (which has now reduced to Bl).

Step6: Since A’s size > new B’s size. So, divide A subarray into other 2 parts – Al and Ar. 

Al is the same size as subarray B from the start, and Ar is the remaining size. 

Step7: Swap elements of subarray Al and B. 

So, AlArB array changes to BArAl in terms of elements, and B subarray elements come at their final position.

Step8: Now, we again compare the size of the remaining non-final subarrays, i.e., A(which reduces to Ar) and B.

Step9: Since A’s size = B’s size, we come out of the loop.

Step10: At the end Block Swap between the elements of subarrays A and B is performed.

Hence, we obtain our final array after rotation of r.

Implementation

Let’s have a look at its implementation in Java –

import java.util.*; 
 
class CodeStudio{ 
    
    // Swapping r elements from starting of index a with r elements starting at index b
    public static void swap(int arr[], int a, int b, int r){ 
        for(int i = 0 ; i < r ; i++){ 
            int temp = arr[a + i]; 
            arr[a + i] = arr[b + i]; 
            arr[b + i] = temp; 
        } 
        
    }
    
    // Left rotating the array elements
    public static void leftRotate(int arr[], int r){ 
        int n = arr.length;
        
        // If the no of elements to rotate = 0 or equal to size of array
        if(r == 0 || r == n) return; 
        
        int i = r; 
        int j = n - r; 
        // Perform block swaps till the size of 2 subarrays is not equal
        while (i != j){   
            // A's size is less
            if(i < j){ 
                swap(arr, r-i, r+j-i, i); 
                j = j - i; 
            } 
            // B's size is less
            else{ 
                swap(arr, r-i, r, j); 
                i = i - j; 
            } 
        }
        
        // Finally at the end, block swap elements of A and B
        swap(arr, r-i, r, i); 
    } 
    
    // Main function
    public static void main(String[] args){ 
        Scanner s = new Scanner(System.in);
        System.out.println("Enter size of the array");
        int n = s.nextInt();
        int[] arr = new int[n];
        
        System.out.println("Enter elements of the array");
        for (int i = 0; i < n; i++) arr[i] = s.nextInt();
        
        System.out.println("Enter the number of rotations");
        int no_of_rotations = s.nextInt();
        
        leftRotate(arr, no_of_rotations); 
        
        System.out.println("Array Elements after rotating : "); 
        for(int i = 0 ; i < n ; i++){   
            System.out.print(arr[i] + " "); 
        }
    }  
}

Output:

Enter the size of the array 
5
Enter elements of the array 
1 2 3 4 5
Enter the number of rotations
2
Array Elements after rotating : 
3 4 5 1 2

Time and Space Complexity

Time Complexity: O(n), In the worst case, k = n – 1, where k is the number of rotations to be performed. So, in the worst-case time complexity the time complexity becomes O(n)

where n is the length of the array.

Space Complexity: O(1) as no extra space has been used.

Frequently Asked Questions

Key Takeaways

In this blog, we learned how to apply Block Swap Algorithm for Array Rotation.. 

• It is an optimized approach for rotating an array by the given number of rotations.
• The approach divides the non-final array into two parts and performs block swap until both the subarrays are of equal size.  
• Its Best Case Time Complexity is O(1), but Worst Case Time Complexity is O(n), where n is the number of elements in an array.

Check out more blogs on different algorithms for Array Rotation to read more about these topics in detail. And if you liked this blog, share it with your friends!

By: Raksha Jain