Block Swap Algorithm for Array Rotation

Block Swap Algorithm for Array Rotation
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.

blog banner 1

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

array

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. 

comparison_of_subarrays

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.

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

comaprison

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.

final_position_of_elements

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

What does the left rotation of an array mean?

The left rotation of an array refers to the anti-clockwise rotation of the elements of an array.

What is the reversal algorithm?

A rotation is an in-place reversal of array elements. Reversal algorithm swaps two elements of an array from outside within a range. The rotation works for an even number of elements or an odd number of array elements. The reversal algorithm uses three in-place rotations to accomplish an in-place block swap:
Rotate region A
Rotate region B
Rotate region AB

What are different algorithms for rotation of arrays?

There are various algorithms for rotating arrays like Juggling Algorithm, Reversal Algorithm, Block Swap Algorithm, etc.

What is Block Swap Algorithm for Array Rotation?

It is one of the optimized algorithms used to rotate an array via swapping two elements of an array in computer algorithms. It divides an array such that it can swap two non-overlapping regions of an array of equal size.

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