Block swap algorithm for array rotation

10 min read

Block swap algorithm is one of the efficient algorithms used for array rotation. Now, let us see about block swap algorithm and a program to rotate an array using the same algorithm.

 

Block Swap Algorithm

  • The algorithm to rotate an array using block swapping algorithm is as follows:
  • Split the input array and initialize arrays A and B as:
    A = arr[0….d-1] and B = arr[d….size-1]     //   d = no_of_rotations
  • Repeat until size of A = size of B.
    • If A is shorter:
      • Divide B into Bl and Br such that Br is of same length as A.   //    Bl = B's left block, Br = B's right block
      • Swap A and Br to change ABlBr into BrBlA.
      • Now A is at its final place. Recur on pieces of B.
    • If A is longer:
      • Divide A into Al and Ar such that Al is of same length as B.   //   Al = A's left block, Ar = A's right block
      • Swap Al and B to change AlArB into BArAl.
      • Now B is at its final place. Recur on pieces of A.
  • Finally when A and B are of equal size, block swap them.

 

C++ program to rotate an array using block swap algorithm

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

/* swaps d elements starting at index a
with d elements starting at index b */
void swap(int arr[], int a, int b, int d)
{
int i, temp;
for(i = 0; i < d; i++)
{
temp = arr[a + i];
arr[a + i] = arr[b + i];
arr[b + i] = temp;
}}

void array_left_rotate(int arr[], int d, int n)
{
int i, j;
if(d == 0 || d == n) // Return the array when no_of_rotations = 0 or n
return;
i = d;
j = n - d;
while (i != j)
{
if(i < j) /*A is shorter*/
{
swap(arr, d-i, d+j-i, i);
j = j - i;
}
else /*B is shorter*/
{
swap(arr, d-i, d, j);
i = i - j;
}}
/*Finally, block swap A and B*/
swap(arr, d-i, d, i);
}
 
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]); // Finding the size of the array
cout<<"\nArray elements before rotating : \n";
for(int i = 0; i < n; i++)
{
cout<<arr[i]<<"\t"; // Printing the array elements
}
int no_of_rotations = 1; // Number of rotations to take place
array_left_rotate(arr, no_of_rotations, n);
cout<<"\n\nArray elements after rotating : \n";
for(int i = 0; i < n; i++)
{
cout<<arr[i]<<"\t"; // Printing the array elements after rotation of elements
}
cout<<"\n";
return 0;
}

 

OUTPUT


block swap algorithm for array rotation


Java program to rotate an array using block swap algorithm

import java.util.Arrays; 

public class Main

/* swaps d elements starting at index a
with d elements starting at index b */
public static void swap(int arr[], int a, int b, int d) 

int i, temp; 
for(i = 0 ; i < d ; i++) 

temp = arr[a + i]; 
arr[a + i] = arr[b + i]; 
arr[b + i] = temp; 
} }

public static void leftRotate(int arr[], int d, int n) 

int i, j; 
if(d == 0 || d == n) 
return; 
i = d; 
j = n - d; 
while (i != j) 

if(i < j) /*A is shorter*/

swap(arr, d-i, d+j-i, i); 
j = j - i; 

else /*B is shorter*/

swap(arr, d-i, d, j); 
i = i - j; 

}
/*Finally, block swap A and B*/
swap(arr, d-i, d, i); 


/* Main Function */
public static void main(String[] args) 

int arr[] = new int[]{1, 2, 3, 4, 5, 6,7}; 
int n = arr.length;
int no_of_rotations = 2;
System.out.println("Array Elements before rotating : "); 
for(int i = 0 ; i < n ; i++)
{
System.out.print(arr[i]+ " "); // Printing elements before rotation
}
leftRotate(arr, no_of_rotations, n); 
System.out.println("\nArray Elements after rotating : "); 
for(int i = 0 ; i < n ; i++)
{
System.out.print(arr[i] + " "); // Printing elements after rotation
}}}

 

Python program to rotate an array using block swap algorithm

/* swaps d elements starting at index a
with d elements starting at index b */
def swap(arr, a, b, d):
for i in range(0,d):
temp = arr[a + i]; 
arr[a + i] = arr[b + i]; 
arr[b + i] = temp; 


def leftRotate(arr, d, n): 
if(d == 0 or d == n): 
return; 
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) 

# Main Function
import array as arr
arr = arr.array('i', [1,2,3,4,5,6,7]) 
print ("The new created array is : ") 
n = len(arr)
no_of_rotations = 2

print("Array Elements before rotation : ")
for i in range (0, n): 
print (arr[i], end = ' ')  # printing original array 

leftRotate(arr, no_of_rotations, n )

print("\nArray Elements after rotation : ")
for i in range (0, n): 
print (arr[i], end = ' ')  # printing array after rotation 
POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error