Table of contents

Introduction

Problem Statement

Recursive Implementation

3.1.

3.2.

C++

3.3.

Java

3.4.

Python

3.5.

Javascript

3.6.

3.7.

Time and Space Complexity

Iterative Implementation

4.1.

4.2.

C++

4.3.

Java

4.4.

Python

4.5.

Javascript

4.6.

4.7.

Time and Space Complexity

Frequently Asked Questions

5.1.

What is meant by swap algorithm?

5.2.

What is the block swap algorithm used for?

5.3.

How do you do a block swap algorithm in Java?

5.4.

What are different algorithms for rotation of arrays?

Conclusion

Last Updated: Jun 2, 2024

Easy

Block Swap Algorithm for Array Rotation

Author Raksha Jain

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

Array rotation is a common operation in computer science that involves shifting the elements of an array to the left or right. One efficient technique to achieve this is the Block Swap Algorithm. This algorithm stands out due to its optimal time complexity and minimal space requirements. By dividing the array into blocks and swapping them strategically, the Block Swap Algorithm ensures a seamless and efficient rotation process.

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.

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

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.

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.

Step5: Now, we again compare the size of the remaining non-final subarrays, i.e., A and B (which has now reduced to Bl).

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.

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.

See more, euclid gcd algorithm

Recursive Implementation

The Block Swap Algorithm rotates an array by swapping blocks of elements. The recursive implementation divides the array into blocks and recursively swaps sub-arrays until the entire array is rotated.

C

#include <stdio.h>

// Function to swap elements
void swap(int arr[], int fi, int si, int d) {
    int temp;
    for (int i = 0; i < d; i++) {
        temp = arr[fi + i];
        arr[fi + i] = arr[si + i];
        arr[si + i] = temp;
    }
}

// Recursive function to rotate array
void rotateArray(int arr[], int i, int j, int d) {
    if (d == 0 || d == j - i) return;
    if (d == j - i - d) {
        swap(arr, i, j - d, d);
        return;
    }

    if (d < j - i - d) {
        swap(arr, i, j - d, d);
        rotateArray(arr, i, j - d, d);
    } else {
        swap(arr, i, i + d, j - i - d);
        rotateArray(arr, i + j - i - d, j, 2 * d - j + i);
    }
}

// Helper function to start the rotation
void blockSwapRotate(int arr[], int n, int d) {
    rotateArray(arr, 0, n, d);
}

// Function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int d = 2;

    blockSwapRotate(arr, n, d);
    printArray(arr, n);

    return 0;
}

You can also try this code with Online C Compiler

Run Code

C++

#include <iostream>
using namespace std;

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

void rotateArray(int arr[], int i, int j, int d) {
    if (d == 0 || d == j - i) return;
    if (d == j - i - d) {
        swap(arr, i, j - d, d);
        return;
    }

    if (d < j - i - d) {
        swap(arr, i, j - d, d);
        rotateArray(arr, i, j - d, d);
    } else {
        swap(arr, i, i + d, j - i - d);
        rotateArray(arr, i + j - i - d, j, 2 * d - j + i);
    }
}

void blockSwapRotate(int arr[], int n, int d) {
    rotateArray(arr, 0, n, d);
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int d = 2;

    blockSwapRotate(arr, n, d);
    printArray(arr, n);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

public class BlockSwapAlgorithm {

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

    static void rotateArray(int[] arr, int i, int j, int d) {
        if (d == 0 || d == j - i) return;
        if (d == j - i - d) {
            swap(arr, i, j - d, d);
            return;
        }

        if (d < j - i - d) {
            swap(arr, i, j - d, d);
            rotateArray(arr, i, j - d, d);
        } else {
            swap(arr, i, i + d, j - i - d);
            rotateArray(arr, i + j - i - d, j, 2 * d - j + i);
        }
    }

    static void blockSwapRotate(int[] arr, int n, int d) {
        rotateArray(arr, 0, n, d);
    }

    static void printArray(int[] arr, int size) {
        for (int i = 0; i < size; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
        int n = arr.length;
        int d = 2;

        blockSwapRotate(arr, n, d);
        printArray(arr, n);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

def swap(arr, fi, si, d):
    for i in range(d):
        arr[fi + i], arr[si + i] = arr[si + i], arr[fi + i]

def rotate_array(arr, i, j, d):
    if d == 0 or d == j - i:
        return
    if d == j - i - d:
        swap(arr, i, j - d, d)
        return

    if d < j - i - d:
        swap(arr, i, j - d, d)
        rotate_array(arr, i, j - d, d)
    else:
        swap(arr, i, i + d, j - i - d)
        rotate_array(arr, i + j - i - d, j, 2 * d - j + i)

def block_swap_rotate(arr, n, d):
    rotate_array(arr, 0, n, d)

def print_array(arr):
    print(" ".join(map(str, arr)))

arr = [1, 2, 3, 4, 5, 6, 7]
n = len(arr)
d = 2

block_swap_rotate(arr, n, d)
print_array(arr)

You can also try this code with Online Python Compiler

Run Code

Javascript

function swap(arr, fi, si, d) {
    for (let i = 0; i < d; i++) {
        let temp = arr[fi + i];
        arr[fi + i] = arr[si + i];
        arr[si + i] = temp;
    }
}

function rotateArray(arr, i, j, d) {
    if (d === 0 || d === j - i) return;
    if (d === j - i - d) {
        swap(arr, i, j - d, d);
        return;
    }

    if (d < j - i - d) {
        swap(arr, i, j - d, d);
        rotateArray(arr, i, j - d, d);
    } else {
        swap(arr, i, i + d, j - i - d);
        rotateArray(arr, i + j - i - d, j, 2 * d - j + i);
    }
}

function blockSwapRotate(arr, n, d) {
    rotateArray(arr, 0, n, d);
}

function printArray(arr) {
    console.log(arr.join(" "));
}

let arr = [1, 2, 3, 4, 5, 6, 7];
let n = arr.length;
let d = 2;

blockSwapRotate(arr, n, d);
printArray(arr);

You can also try this code with Online Javascript Compiler

Run Code

C#

using System;

class BlockSwapAlgorithm
{
    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;
        }
    }

    static void RotateArray(int[] arr, int i, int j, int d) {
        if (d == 0 || d == j - i) return;
        if (d == j - i - d) {
            Swap(arr, i, j - d, d);
            return;
        }

        if (d < j - i - d) {
            Swap(arr, i, j - d, d);
            RotateArray(arr, i, j - d, d);
        } else {
            Swap(arr, i, i + d, j - i - d);
            RotateArray(arr, i + j - i - d, j, 2 * d - j + i);
        }
    }

    static void BlockSwapRotate(int[] arr, int n, int d) {
        RotateArray(arr, 0, n, d);
    }

    static void PrintArray(int[] arr, int size) {
        for (int i = 0; i < size; i++)
            Console.Write(arr[i] + " ");
        Console.WriteLine();
    }

    static void Main() {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
        int n = arr.Length;
        int d = 2;

        BlockSwapRotate(arr, n, d);
        PrintArray(arr, n);
    }
}

Output

3 4 5 6 7 1 2

Time and Space Complexity

Time Complexity: 𝑂(𝑛)O(n), where 𝑛n is the number of elements in the array. Each element is moved at most once.
Space Complexity: 𝑂(1)O(1), no extra space is used other than the recursion stack.

Iterative Implementation

C

#include <stdio.h>

// Function to swap elements
void swap(int arr[], int fi, int si, int d) {
    int temp;
    for (int i = 0; i < d; i++) {
        temp = arr[fi + i];
        arr[fi + i] = arr[si + i];
        arr[si + i] = temp;
    }
}

// Iterative function to rotate array
void blockSwapRotate(int arr[], int n, int d) {
    if (d == 0 || d == n) return;

    int i = d, j = n - d;
    while (i != j) {
        if (i < j) { // A is shorter
            swap(arr, d - i, d + j - i, i);
            j -= i;
        } else { // B is shorter
            swap(arr, d - i, d, j);
            i -= j;
        }
    }
    swap(arr, d - i, d, i);
}

// Function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int d = 2;

    blockSwapRotate(arr, n, d);
    printArray(arr, n);

    return 0;
}

You can also try this code with Online C Compiler

Run Code

C++

#include <iostream>
using namespace std;

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

void blockSwapRotate(int arr[], int n, int d) {
    if (d == 0 || d == n) return;

    int i = d, j = n - d;
    while (i != j) {
        if (i < j) {
            swap(arr, d - i, d + j - i, i);
            j -= i;
        } else {
            swap(arr, d - i, d, j);
            i -= j;
        }
    }
    swap(arr, d - i, d, i);
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int d = 2;

    blockSwapRotate(arr, n, d);
    printArray(arr, n);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

public class BlockSwapAlgorithm {

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

    static void blockSwapRotate(int[] arr, int n, int d) {
        if (d == 0 || d == n) return;

        int i = d, j = n - d;
        while (i != j) {
            if (i < j) {
                swap(arr, d - i, d + j - i, i);
                j -= i;
            } else {
                swap(arr, d - i, d, j);
                i -= j;
            }
        }
        swap(arr, d - i, d, i);
    }

    static void printArray(int[] arr, int size) {
        for (int i = 0; i < size; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
        int n = arr.length;
        int d = 2;

        blockSwapRotate(arr, n, d);
        printArray(arr, n);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

def swap(arr, fi, si, d):
    for i in range(d):
        arr[fi + i], arr[si + i] = arr[si + i], arr[fi + i]

def block_swap_rotate(arr, n, d):
    if d == 0 or d == n:
        return

    i, j = d, n - d
    while i != j:
        if i < j:
            swap(arr, d - i, d + j - i, i)
            j -= i
        else:
            swap(arr, d - i, d, j)
            i -= j
    swap(arr, d - i, d, i)

def print_array(arr):
    print(" ".join(map(str, arr)))

arr = [1, 2, 3, 4, 5, 6, 7]
n = len(arr)
d = 2

block_swap_rotate(arr, n, d)
print_array(arr)

You can also try this code with Online Python Compiler

Run Code

Javascript

function swap(arr, fi, si, d) {
    for (let i = 0; i < d; i++) {
        let temp = arr[fi + i];
        arr[fi + i] = arr[si + i];
        arr[si + i] = temp;
    }
}

function blockSwapRotate(arr, n, d) {
    if (d === 0 || d === n) return;

    let i = d, j = n - d;
    while (i !== j) {
        if (i < j) {
            swap(arr, d - i, d + j - i, i);
            j -= i;
        } else {
            swap(arr, d - i, d, j);
            i -= j;
        }
    }
    swap(arr, d - i, d, i);
}

function printArray(arr) {
    console.log(arr.join(" "));
}

let arr = [1, 2, 3, 4, 5, 6, 7];
let n = arr.length;
let d = 2;

blockSwapRotate(arr, n, d);
printArray(arr);

You can also try this code with Online Javascript Compiler

Run Code

C#

using System;

class BlockSwapAlgorithm
{
    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;
        }
    }

    static void BlockSwapRotate(int[] arr, int n, int d) {
        if (d == 0 || d == n) return;

        int i = d, j = n - d;
        while (i != j) {
            if (i < j) {
                Swap(arr, d - i, d + j - i, i);
                j -= i;
            } else {
                Swap(arr, d - i, d, j);
                i -= j;
            }
        }
        Swap(arr, d - i, d, i);
    }

    static void PrintArray(int[] arr, int size) {
        for (int i = 0; i < size; i++)
            Console.Write(arr[i] + " ");
        Console.WriteLine();
    }

    static void Main() {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
        int n = arr.Length;
        int d = 2;

        BlockSwapRotate(arr, n, d);
        PrintArray(arr, n);
    }
}

Output

3 4 5 6 7 1 2

Time and Space Complexity

Time Complexity: 𝑂(𝑛)O(n), each element is moved at most once.
Space Complexity: 𝑂(1)O(1), no extra space is used.

Also see, Morris Traversal for Inorder and Rabin Karp Algorithm

Frequently Asked Questions

What is meant by swap algorithm?

A swap algorithm exchanges the values of two variables, typically using a temporary variable to hold one value during the exchange.

What is the block swap algorithm used for?

The block swap algorithm is used to rotate an array efficiently by swapping blocks of elements instead of individual elements.

How do you do a block swap algorithm in Java?

Implement the block swap algorithm in Java by dividing the array into blocks, swapping these blocks recursively or iteratively to achieve rotation.

What are different algorithms for rotation of arrays?

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

Conclusion

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.

Recommended Readings:

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!

Live masterclass

Become a YouTube Analyst: Use Python to analyze viewers data

by Coding Ninjas

04 Feb, 2025

02:30 PM

84+ registered

Get hired as an Amazon SDE : Resume building tips

by Coding Ninjas

03 Feb, 2025

02:30 PM

375+ registered

Expert tips: Ace Leadership roles in Fortune 500 companies

by Coding Ninjas

03 Feb, 2025

12:30 PM

71+ registered

Become a YouTube Analyst: Use Python to analyze viewers data

by Coding Ninjas

04 Feb, 2025

02:30 PM

84+ registered

Get hired as an Amazon SDE : Resume building tips

by Coding Ninjas

03 Feb, 2025

02:30 PM

375+ registered

View more events