Java program for Block swapping algorithm for array rotation

Block swap algorithm for array rotation

Here in this program we will be learning about Block swap algorithm. It is one of the most efficient algorithms used for array rotation. Now, let’s discuss about block swap algorithm and a program to rotate an array using the same algorithm.

Example.

Arr: {0,1,2,3,4}

After block swapping

{3,4,2,1,0}

java program for Block swap algorithm for array rotation

Algorithm

The algorithm to rotate an array using block swapping algorithm are:-

     step 1- Initialize array A and B and then split them

    Step 2 -A = arr[0….d-1] and B = arr[d….size-1]   //  d = no_of_rotations

    Step 3-Repeat until size of A = size of B.

    a- If A is shorter:

    b- 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

    Step 4- Swap A and Br to change ABlBr into BrBlA.

     Step 5- Now A is at its final place. Recur on pieces of B.

    Step 6-If A is longer:

    a- 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

    b- Swap Al and B to change AlArB into BArAl.

     Step 7- Now B is at its final place. Recur on pieces of A.

Java program

 

import java.util.Arrays;

public class PrepInsta  
{ 
      public static void swap(int arr[], int x, int y, int z) 
    { 
        int i, temp; 
        for(i = 0 ; i < z ; i++) 
        { 
            temp = arr[a + i]; 
            arr[a + i] = arr[b + i]; 
            arr[y + i] = temp; 
        } }

    public static void leftRotate(int arr[], int z, int n) 
    { 
        int i, j; 
        if(z == 0 || z == n) 
            return; 
        i = z; 
        j = n - z; 
        while (i != j) 
        { 
            if(i < j) //A is shorter
            { 
                swap(arr, z-i, z+j-i, i); 
                j = j - i; 
            } 
            else //B is shorter
            { 
                swap(arr, z-i, z, j); 
                i = i - j; 
            } 
        }
        //Block swap A and B
        swap(arr, z-i, z, 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 = 5;
        System.out.println(" Elements of Array 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("Elements of Array after rotating : "); 
        for(int i = 0 ; i < n ; i++)
        {
            System.out.print(arr[i] + " "); // Printing elements after rotation
               }
}
}
output
Enter Elements of array 
{1,2,3,4,5,6,7}
After swapping 
6,7,1,2,3,4,5