Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Recursive Implementation
3.1.
C
3.2.
C++
3.3.
Java
3.4.
Python
3.5.
Javascript
3.6.
C#
3.7.
Time and Space Complexity
4.
Iterative Implementation
4.1.
C
4.2.
C++
4.3.
Java
4.4.
Python
4.5.
Javascript
4.6.
C#
4.7.
Time and Space Complexity
5.
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?
6.
Conclusion
Last Updated: Jun 2, 2024
Easy

Block Swap Algorithm for Array Rotation

Author Raksha Jain
1 upvote
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

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. 

Block Swap Algorithm

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
 

array

 

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. 

comparison_of_subarrays

 

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.

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).

comaprison

 

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.
 

final_position_of_elements

 

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.
 

array


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.

final output

See more, euclid gcd algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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
  • C++
  • Java
  • Python
  • Javascript
  • C#

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

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

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

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)

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

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
  • C++
  • Java
  • Python
  • Javascript
  • C#

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

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

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

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)

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

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