Example: Block Swap Array Rotation in C++

// 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;
}