Block Swap Algorithm For Array Rotation In C++ Program

Array rotation is a fundamental operation in data manipulation, involving shifting the elements of an array by a specified number of positions. While seemingly simple, optimizing this process is crucial for performance in applications dealing with large datasets. In this article, you will learn how to efficiently rotate an array using the Block Swap algorithm in C++.

Problem Statement

Given an array arr of size n and an integer d, the task is to rotate the array to the left by d positions. This means the first d elements of the array should move to the end, and the remaining elements shift to the beginning. For example, if an array [1, 2, 3, 4, 5, 6, 7] is rotated left by 2 positions, it should become [3, 4, 5, 6, 7, 1, 2]. Naive approaches, such as repeatedly shifting one element at a time, can lead to O(n*d) time complexity, which is inefficient for large d or n.

Example

Consider the array [1, 2, 3, 4, 5, 6, 7] rotated by d = 2.

• Original Array: [1, 2, 3, 4, 5, 6, 7]
• Rotated by 2: [3, 4, 5, 6, 7, 1, 2]

 

Background & Knowledge Prerequisites

To understand and implement the Block Swap algorithm, readers should have a basic understanding of:

• C++ fundamentals: Variables, data types, loops, and functions.
• Arrays/Vectors: How to declare, initialize, access, and manipulate elements in C++.
• Recursion: The concept of a function calling itself.

 

Relevant C++ standard library includes:

• iostream for input/output.
• vector for dynamic array usage.
• algorithm for std::swap.

 

Use Cases or Case Studies

Array rotation finds applications in various domains:

• Image Processing: In image filters or transformations, sometimes pixel data needs to be shifted circularly.
• Data Encryption: Simple forms of data scrambling might involve rotating blocks of data.
• Circular Buffers/Queues: Implementing fixed-size circular data structures where new elements replace old ones, simulating a rotating window.
• Game Development: Rotating game board elements or character positions on a circular path.
• Algorithm Optimization: As a subroutine in more complex algorithms that require data rearrangement.

 

Solution Approaches

While several methods exist for array rotation (like juggling algorithm, reversal algorithm), the Block Swap algorithm is known for its efficiency and recursive elegance.

Block Swap Algorithm

The Block Swap algorithm is a recursive method that rotates an array by dividing it into two blocks and repeatedly swapping parts of these blocks until the array is rotated. It aims for O(n) time complexity and O(log n) or O(1) auxiliary space (depending on whether recursion stack is counted).

One-line Summary

The Block Swap algorithm recursively partitions the array into two sub-blocks, 'A' (the first d elements) and 'B' (the remaining n-d elements), then repeatedly swaps the smaller sub-block with an equal-sized part of the larger sub-block until the entire array is rotated.

Code Example

// Block Swap Array Rotation
#include <iostream>
#include <vector>    // For std::vector
#include <algorithm> // For std::swap

// Helper function to print the array
void printArray(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

// Helper function to swap two blocks of 'len' elements
// starting at index 'i' and 'j' respectively.
void swapBlocks(std::vector<int>& arr, int i, int j, int len) {
    for (int k = 0; k < len; ++k) {
        std::swap(arr[i + k], arr[j + k]);
    }
}

// Recursive function to perform block swap rotation
// current_start_idx: The starting index of the current sub-array segment
// current_len: The total length of the current sub-array segment
// d: The number of positions to rotate by within this segment
void _blockSwap(std::vector<int>& arr, int current_start_idx, int current_len, int d) {
    // Base cases
    d %= current_len; // Ensure d is within the current_len bounds
    if (d == 0 || d == current_len) {
        return; // No rotation needed
    }

    // Let the current segment be [A][B]
    // A: arr[current_start_idx ... current_start_idx + d - 1]
    // B: arr[current_start_idx + d ... current_start_idx + current_len - 1]
    int len_A = d;
    int len_B = current_len - d;

    if (len_A == len_B) {
        // Case 1: A and B are of equal length. Just swap them.
        swapBlocks(arr, current_start_idx, current_start_idx + len_A, len_A);
    } else if (len_A < len_B) {
        // Case 2: A is shorter than B.
        // Swap A with the last 'len_A' elements of B (B2).
        // B = [B1][B2], where B1 has length (len_B - len_A) and B2 has length len_A.
        // Swap A (at current_start_idx) with B2 (at current_start_idx + len_B).
        swapBlocks(arr, current_start_idx, current_start_idx + len_B, len_A);

        // After swapping, the array segment becomes [B2][B1][A].
        // Now, the new problem is to rotate the prefix [B2][B1] (effectively B) by 'len_A' positions.
        // This means rotating arr[current_start_idx ... current_start_idx + len_B - 1] by len_A.
        _blockSwap(arr, current_start_idx, len_B, len_A);
    } else { // len_A > len_B
        // Case 3: A is longer than B.
        // Swap B with the last 'len_B' elements of A (A2).
        // A = [A1][A2], where A1 has length (len_A - len_B) and A2 has length len_B.
        // Swap B (at current_start_idx + len_A) with A2 (at current_start_idx + len_A).
        swapBlocks(arr, current_start_idx, current_start_idx + len_A, len_B);

        // After swapping, the array segment becomes [B][A1][A2].
        // Now, the new problem is to rotate the suffix [A1][A2] (effectively A) by (len_A - len_B) positions.
        // This means rotating arr[current_start_idx + len_B ... current_start_idx + current_len - 1]
        // by (len_A - len_B) positions.
        _blockSwap(arr, current_start_idx + len_B, len_A, len_A - len_B);
    }
}

// Wrapper function for the Block Swap algorithm
void rotateArrayBlockSwap(std::vector<int>& arr, int d) {
    int n = arr.size();
    if (n == 0) return;
    _blockSwap(arr, 0, n, d);
}

int main() {
    // Step 1: Initialize array and rotation amount
    std::vector<int> arr1 = {1, 2, 3, 4, 5, 6, 7};
    int d1 = 2; // Rotate by 2 positions

    std::cout << "Original array: ";
    printArray(arr1);

    // Step 2: Apply the Block Swap algorithm
    rotateArrayBlockSwap(arr1, d1);

    // Step 3: Print the rotated array
    std::cout << "Rotated array by " << d1 << " positions: ";
    printArray(arr1);
    std::cout << std::endl;

    // Test with another example: d > n
    std::vector<int> arr2 = {10, 20, 30, 40, 50};
    int d2 = 7; // Rotate by 7 positions (effectively 7 % 5 = 2)

    std::cout << "Original array: ";
    printArray(arr2);
    rotateArrayBlockSwap(arr2, d2);
    std::cout << "Rotated array by " << d2 << " positions: ";
    printArray(arr2);
    std::cout << std::endl;

    // Test with d = 0 or d = n
    std::vector<int> arr3 = {1, 2, 3};
    int d3 = 0;
    std::cout << "Original array: ";
    printArray(arr3);
    rotateArrayBlockSwap(arr3, d3);
    std::cout << "Rotated array by " << d3 << " positions: ";
    printArray(arr3);
    std::cout << std::endl;

    std::vector<int> arr4 = {1, 2, 3};
    int d4 = 3;
    std::cout << "Original array: ";
    printArray(arr4);
    rotateArrayBlockSwap(arr4, d4);
    std::cout << "Rotated array by " << d4 << " positions: ";
    printArray(arr4);
    std::cout << std::endl;

    return 0;
}

Run

Sample Output

Original array: 1 2 3 4 5 6 7 
Rotated array by 2 positions: 3 4 5 6 7 1 2 

Original array: 10 20 30 40 50 
Rotated array by 7 positions: 30 40 50 10 20 

Original array: 1 2 3 
Rotated array by 0 positions: 1 2 3 

Original array: 1 2 3 
Rotated array by 3 positions: 1 2 3

 

Stepwise Explanation for Clarity

1. rotateArrayBlockSwap(arr, d) Wrapper: This function takes the array and the rotation count d. It initializes the recursive process by calling _blockSwap with the entire array (arr, starting at index 0, total length n, and rotation d).

1. _blockSwap(arr, current_start_idx, current_len, d) Recursive Function:
   • Normalize d: d %= current_len ensures d is within the bounds of the current segment's length. If d becomes 0 after this (or if initially d was 0 or equal to current_len), no rotation is needed, so it returns.

• Define Blocks A and B: The current segment of the array (arr[current_start_idx ... current_start_idx + current_len - 1]) is conceptually divided into two parts:
• Block A: The first d elements.
• Block B: The remaining current_len - d elements.
• Case 1: len_A == len_B (Equal Lengths): If both blocks are of the same size, a single swapBlocks operation between A and B suffices to rotate them.
• Case 2: len_A < len_B (A is Shorter):
• Block B is further divided into B1 (first len_B - len_A elements) and B2 (last len_A elements).
• swapBlocks is performed between A and B2. This places B2 at the beginning, followed by B1, then A. The segment becomes [B2][B1][A].
• The problem then reduces to rotating the [B2][B1] part (which is len_B elements long) by len_A positions. A recursive call _blockSwap(arr, current_start_idx, len_B, len_A) handles this.
• Case 3: len_A > len_B (A is Longer):
• Block A is further divided into A1 (first len_A - len_B elements) and A2 (last len_B elements).
• swapBlocks is performed between B and A1. This places B at the beginning, followed by A1, then A2. The segment becomes [B][A1][A2].
• The problem then reduces to rotating the [A1][A2] part (which is len_A elements long) by len_A - len_B positions. A recursive call _blockSwap(arr, current_start_idx + len_B, len_A, len_A - len_B) handles this.

1. swapBlocks(arr, i, j, len) Helper: This utility function simply swaps len elements starting from index i with len elements starting from index j. It uses std::swap for individual element swaps.

This recursive process continues until d becomes 0 or equal to the current segment's length, at which point the rotation for that segment is complete.

Conclusion

The Block Swap algorithm offers an efficient way to rotate an array, achieving O(n) time complexity with O(log n) auxiliary space (due to recursion stack depth). Its recursive nature elegantly handles the rearrangement of blocks by repeatedly reducing the problem into smaller subproblems. While perhaps less intuitive than simple reversal or juggling algorithms for some, it demonstrates a powerful divide-and-conquer approach to array manipulation.

Summary

• Array rotation shifts elements by d positions.
• The Block Swap algorithm is a recursive approach for O(n) time complexity.
• It works by dividing the array into two conceptual blocks (first d elements and remaining n-d elements).
• The algorithm recursively swaps the smaller block with a corresponding part of the larger block until the entire array is rotated.
• Key operations involve defining block lengths, conditionally swapping, and making recursive calls on reduced subproblems.