Home » Data Structure » Array Data Structure

Block Swap Algorithm for Array Rotation

Learn about the block swap algorithm for array rotation and its implementation using C++ programs.
Submitted by Vikneshwar GK, on February 14, 2022

Array Rotation

Consider an integer array of size n and an integer d. The task at hand is to rotate the elements anti-clockwise by d elements, i.e., place the first d elements at the end of the array by pushing the remaining elements to the front.

Example:

Input:
array[]= {1, 2, 3, 4, 5}
d = 3

Output:
array[] = {4, 5, 1, 2, 3}

Input:
array[]= {10, 20, 30, 40, 50}
d = 1

Output: array[]= {20, 30, 40, 50, 10}

Block Swap Algorithm

This algorithm involves the array to be split into blocks and working on them individually to get the desired result. It involves the following steps:

• Split the into two groups, G1 = array[0..d-1] and G2 = array[d..n-1]
• If the length of G1 is lesser than G2, then split G2 into two groups, G2L and G2R, in such a way that the size of G1 is the same as G2R. Swap G1 and G2R. The order of array will look like, G2R, G2L, G1.
• If the length of G1 is greater than G2, then split G1 into two groups, G1L and G1R, in such a way that the size of G2 is the same as G1L. Swap G2 and G1L. The order of array will look like, G2, G1R, G1L.
• Repeat the above steps until the size of G1 is equal to G2
• Print the array

Solution 1: Using Recursion

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

// function declaration
void swap(int array[], int group1, int, int d);

// Function to rotate array
// using block swap
void rotate(int array[], int d, int length)
{
    // null check
    if (d == 0 || d == length)
        return;

    // case to handle when d greater than length
    if (d > length)
        d = d % length;

    // if two groups size are equal
    // swap once
    if (length - d == d) {
        swap(array, 0, length - d, d);
        return;
    }

    // group 1 is shorter
    if (d < length - d) {
        swap(array, 0, length - d, d);
        rotate(array, d, length - d);
    }
    // group 2 is shorter
    else {
        swap(array, 0, d, length - d);
        rotate(array + length - d, 2 * d - length, d);
    }
}

// function to swap the array
void swap(int array[], int group1, int group2, int d)
{
    int i, temp;
    for (i = 0; i < d; i++) {
        temp = array[group1 + i];
        array[group1 + i] = array[group2 + i];
        array[group2 + i] = temp;
    }
}

//Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++)
        cout << array[i] << " ";
    cout << endl;
}

// Main function
int main()
{
    int array[100], N, d;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }
    cout << "Enter the value of d: ";
    cin >> d;

    rotate(array, d, N);
    cout << "Rotated Array" << endl;
    printArray(array, N);

    return 0;
}

Output:

Enter Number of elements: 6
Enter element 1:2
Enter element 2:4
Enter element 3:6
Enter element 4:8
Enter element 5:10
Enter element 6:12
Enter the value of d: 3
Rotated Array
8 10 12 2 4 6 

Solution 2: Using while-loop

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

// function declaration
void swap(int array[], int group1, int, int d);

// Function to rotate array
// using block swap
void rotate(int array[], int d, int length)
{
    int i, j;

    // null check
    if (d == 0 || d == length)
        return;

    // case to handle when d greater than length
    if (d > length)
        d = d % length;

    i = d;
    j = length - d;

    while (i != j) {
        // group 1 is shorter
        if (i < j) {
            swap(array, d - i, d + j - i, i);
            j -= i;
        }
        // group 2 is shorter
        else {
            swap(array, d - i, d, j);
            i -= j;
        }
    }
    swap(array, d - i, d, i);
}

// function to swap the array
void swap(int array[], int group1, int group2, int d)
{
    int i, temp;
    for (i = 0; i < d; i++) {
        temp = array[group1 + i];
        array[group1 + i] = array[group2 + i];
        array[group2 + i] = temp;
    }
}

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++)
        cout << array[i] << " ";
    cout << endl;
}

// Main function
int main()
{
    int array[100], N, d;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }
    cout << "Enter the value of d: ";
    cin >> d;

    rotate(array, d, N);
    cout << "Rotated Array" << endl;
    printArray(array, N);
    
    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1:5
Enter element 2:4
Enter element 3:3
Enter element 4:2
Enter element 5:1
Enter the value of d: 2
Rotated Array
3 2 1 5 4 

Time Complexity: O(n), where n is the length of the array.