Block swap algorithm for array rotation in Java

In this tutorial, we’ll learn the block swap algorithm for array rotation (left) in Java.
Consider a given array (a) :

1,  2,  3,  4,  5,  6,  7,  8,  9

After rotating the array by d=4, we get,

5,  6,  7,  8,  9,  1,  2,  3,  4

Approach:

The approach to solving the problem is as follows :

• Create 2 arrays A and B where A is from 0 to d-1 and B is from d to n-1 (last index of the array).
• Now compare both arrays A and B.
• If the size of A is smaller than B then divide array B into 2 parts B1 and B2 such that the size of B2 is equal to the size of A. Then perform swap operation on A and B2. Hence, the array becomes B2B1A. Thus, the position of the array A is now fixed.
• If the size of B is smaller than A then divide array A into 2 parts A1 and A2 such that the size of A1 is equal to the size of B. Then perform swap operation on A1 and B. Hence, the array becomes BA2A1. Thus, the position of the array B is now fixed.
• Keep on performing the above steps until the size of A equals the size of B.
• After each step, a smaller array is fixed in its proper position and by repeating the above steps we get the desired array.
• Now, when the size of A equal B, perform the last swap operation on both of them.

Implementation :

The code for the above approach is as follows :

import java.util.*;
import java.lang.*;
import java.io.*;
class CodeSpeedy 
{
    public static void Rotation(int a[],int d,int n)  
    {  
        if(d==0||d==n)  
            return;  
        int i=d;  
        int j=n-d;  
        while(i!=j)  
        {  
            int x=d-i;
            if(i<j)
            {  
                int y=d+j-i;
                swapping(a,x,y,i);  
                j=j-i;  
            }  
            else 
            {  
                swapping(a,x,d,j);  
                i=i-j;  
            }  
        }  
        swapping(a,d-i,d,i);  
    } 
    public static void swapping(int a[],int x,int y,int d)  
    {
        for(int i=0;i<d;i++)  
        {  
            int temp=a[x+i];  
            a[x+i]=a[y+i];  
            a[y+i]=temp;
        } 
    }  
    public static void main (String[] args)  
    { 
        int a[]={1,2,3,4,5,6,7,8,9};  
        Rotation(a,4,9); 
        for(int i=0;i<9;i++)  
            System.out.print(a[i]+" ");  
    } 
}

 

Output :
5 6 7 8 9 1 2 3 4

 

Recommended Posts:

Block swap algorithm for rotation of the array

How to swap both diagonals of a matrix in C++