Block Swap Algorithm For Array Rotation In Java Program

Array rotation is a fundamental operation in computer science, often used in algorithms for data manipulation and processing. In this article, you will learn about the Block Swap Algorithm, an efficient method for rotating arrays by a specified number of positions, and explore its implementation in Java.

Problem Statement

Rotating an array means shifting its elements cyclically. If an array [1, 2, 3, 4, 5] is rotated by two positions, it becomes [3, 4, 5, 1, 2]. This operation is crucial in various computational tasks, but inefficient rotation can lead to performance bottlenecks, especially with large datasets. The challenge is to perform this rotation in an optimal time and space complexity.

Example

Consider an array arr = [10, 20, 30, 40, 50, 60, 70] and a rotation count d = 3. The rotated array will be: [40, 50, 60, 70, 10, 20, 30]

Background & Knowledge Prerequisites

To understand array rotation algorithms, readers should be familiar with:

• Java Basics: Variables, loops (for, while), conditional statements (if-else).
• Arrays: Declaration, initialization, accessing elements, length property.
• Methods/Functions: Defining and calling methods.

No special imports or complex data structures are required beyond basic Java.

Use Cases or Case Studies

Array rotation finds applications in several areas:

• Data Encryption: Permuting data elements to enhance security.
• Image Processing: Rotating pixel matrices for image manipulation.
• Algorithm Optimization: As a subroutine in more complex algorithms like searching in a rotated sorted array.
• Circular Buffers: Implementing data structures where the oldest elements are overwritten by new ones in a cyclical fashion.
• Game Development: Shifting game board elements or character animations.

Solution Approaches

There are several ways to rotate an array, each with its own trade-offs in terms of time and space complexity.

• Naive Approach: Create a temporary array, copy elements from the rotation point, then copy the remaining elements. This is simple but uses O(n) extra space.
• One-by-One Rotation: Rotate the array by one position d times. This is O(n*d) time complexity, which is inefficient for large d.
• Reversal Algorithm: This method involves three steps of reversing subarrays. It's an O(n) time and O(1) space complexity solution.
• Juggling Algorithm: Using the greatest common divisor (GCD) of n and d, elements are moved in gcd(n, d) cycles. This is an O(n) time and O(1) space complexity solution.

For a specific and efficient approach, we will focus on the Block Swap Algorithm.

Block Swap Algorithm

The Block Swap Algorithm is a recursive method for array rotation that can be more intuitive for some to grasp than the Juggling algorithm, though both achieve O(n) time complexity with O(1) auxiliary space (if recursion stack space is ignored, or tail recursion is optimized). It works on the principle of repeatedly swapping blocks of elements.

One-line summary: Recursively swap two blocks of array elements until the array is rotated by the desired number of positions.

// Block Swap Array Rotation
import java.util.Arrays; // For printing the array easily

// Main class containing the entry point of the program
public class Main {

    /**
     * Reverses a subarray from index 'start' to 'end'.
     * This is a helper method often used in array manipulations.
     */
    private static void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }

    /**
     * Swaps two blocks of elements within the array.
     * Block 1: arr[fi...fi+d-1]
     * Block 2: arr[si...si+d-1]
     */
    private static void swap(int[] arr, int fi, int si, int d) {
        for (int i = 0; i < d; i++) {
            int temp = arr[fi + i];
            arr[fi + i] = arr[si + i];
            arr[si + i] = temp;
        }
    }

    /**
     * Rotates an array left by 'd' positions using the Block Swap Algorithm.
     *
     * @param arr The array to be rotated.
     * @param d   The number of positions to rotate (left).
     * @param n   The total number of elements in the array.
     */
    public static void rotateArrayBlockSwap(int[] arr, int d, int n) {
        // Ensure d is within the bounds [0, n-1]
        d = d % n;
        if (d == 0 || d == n) {
            return; // No rotation needed
        }

        // Base case: if one block is smaller, swap and recurse for remaining
        if (d == n - d) { // Blocks are of equal size
            swap(arr, 0, n - d, d);
            return;
        }

        // A is for first d elements, B is for remaining n-d elements
        // If A is shorter than B
        if (d < n - d) {
            swap(arr, 0, n - d, d); // Swap A with a part of B
            rotateArrayBlockSwap(arr, d, n - d); // Rotate remaining part of B
        }
        // If A is longer than B
        else {
            swap(arr, 0, d, n - d); // Swap B with a part of A
            rotateArrayBlockSwap(arr, d - (n - d), d); // Rotate remaining part of A
        }
    }

    public static void main(String[] args) {
        // Step 1: Define the array and rotation count
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        int d = 2; // Rotate by 2 positions to the left
        int n = arr.length;

        System.out.println("Original array: " + Arrays.toString(arr));

        // Step 2: Call the block swap rotation function
        rotateArrayBlockSwap(arr, d, n);

        // Step 3: Print the rotated array
        System.out.println("Array after " + d + " rotations: " + Arrays.toString(arr));

        System.out.println("\\n--- Another Example ---");
        int[] arr2 = {10, 20, 30, 40, 50, 60, 70, 80};
        int d2 = 3;
        int n2 = arr2.length;
        System.out.println("Original array: " + Arrays.toString(arr2));
        rotateArrayBlockSwap(arr2, d2, n2);
        System.out.println("Array after " + d2 + " rotations: " + Arrays.toString(arr2));
    }
}

Run

Sample output:

Original array: [1, 2, 3, 4, 5, 6, 7]
Array after 2 rotations: [3, 4, 5, 6, 7, 1, 2]

--- Another Example ---
Original array: [10, 20, 30, 40, 50, 60, 70, 80]
Array after 3 rotations: [40, 50, 60, 70, 80, 10, 20, 30]

Stepwise explanation:

1. rotateArrayBlockSwap(int[] arr, int d, int n) Function:

• This is the main recursive function. d is the number of elements to rotate, and n is the total size of the array.
• It first normalizes d to be within [0, n-1] using the modulo operator. If d is 0 or n, no rotation is needed, so it returns.

1. Base Case (d == n - d):

• If the block A (size d) and block B (size n-d) are of equal length, the algorithm simply swaps them directly. For example, if n=6, d=3, A=[1,2,3], B=[4,5,6], they are swapped to [4,5,6,1,2,3].

1. Recursive Cases:

• The array is conceptualized as A (first d elements) and B (remaining n-d elements). We want to achieve BA.
• Case 1: d < n - d (Block A is shorter than Block B):
• We swap the first d elements of A with the last d elements of B. The array becomes [B2 | A | B1].
• Example: [1,2,3 | 4,5,6,7] (d=3, n=7). Swap [1,2,3] with [5,6,7] -> [5,6,7 | 4 | 1,2,3].
• Now, A is in its correct place. We need to rotate the remaining n-d elements (which are B1 and the remainder of B2) by d positions. The recursive call is rotateArrayBlockSwap(arr, d, n - d), operating on the subarray starting from index d.
• Case 2: d > n - d (Block A is longer than Block B):
• We swap the first n-d elements of A with B. The array becomes [B | A1 | A2].
• Example: [1,2,3,4,5 | 6,7] (d=5, n=7). Swap [1,2] with [6,7] -> [6,7 | 3,4,5 | 1,2].
• Now, B is in its correct place. We need to rotate the remaining d elements (which are A1 and A2) by d - (n - d) positions. The recursive call is rotateArrayBlockSwap(arr, d - (n - d), d), operating on the subarray starting from index n-d.

1. swap(int[] arr, int fi, int si, int d) Function:

• A helper function that performs an in-place swap of two blocks of d elements. fi is the starting index of the first block, si is the starting index of the second block.

The recursion continues until the base case is met or the d becomes 0 or n, effectively rotating the entire array.

Conclusion

The Block Swap Algorithm offers an efficient, in-place method for array rotation with a time complexity of O(n) and O(log n) space complexity due to recursion stack (O(1) if optimized for tail recursion or implemented iteratively). It provides a structured approach to solving the array rotation problem by breaking it down into smaller, manageable block swaps, making it a valuable tool in a developer's arsenal for optimizing data manipulation tasks.

Summary

• Array rotation is a fundamental operation in programming.
• The Block Swap Algorithm rotates an array left by d positions.
• It operates by recursively swapping blocks of elements.
• The algorithm handles cases where the blocks are of equal or unequal sizes.
• It has an O(n) time complexity and uses O(log n) space due to recursion.
• The swap helper method facilitates the block exchange.
• This method is an efficient alternative to naive or one-by-one rotation approaches.