Block Swap Algorithm for array rotation in Java
An array and r, the rotation factor by which the array must be rotated, are both provided to us. We must then return the rotated array.
A well-known and popular method is Block Swap Algorithm for Array Rotation.
Example
Input
int array [ ] = {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,9 } , n = 9 , r = 3
Output
answer [ ] = { 4 , 5 , 6 , 7 , 8 ,9 ,1 , 2 , 3 }Explanation
The input array's size, n, is explained. We must rotate the array three times if r = 3. The first time we rotate, we get the numbers 2, 3, 4, 5, 6, 7, 8, 9, and 1. Now, after rotating the array a second time, we obtain the values 3, 4, 5, 6, 7, 8, 9, 1, and 2. The third rotation is now required. We get {4 , 5 , 6 , 7 , 8 , 9 ,1 , 2 , 3 }
Block Swap Algorithm
Step 1:
First, use div as the division point to split the input array into two smaller arrays. Let A = arr[0... div - 1] and B = arr[div... n - 1] be their respective values.
Step 2:
Repeat the following procedures up until the sizes of A and B are equal:
Divide A into two sections, A1 and A2, so that the size of A1 is equal to the size of A2, if A is larger than B. Change the A1 and B sub-arrays. The array is altered from A1A2B to BA2A1.
If the size of B is more than the size of A, divide B into B1 and B2, making sure that B2 has the same size as B. Alternate the A and B2 subarrays. The array is changed from AB1B2 to B2B1A.
Step 3: Switch the sizes of A and B when they are equal.
Using Recursion
Program to rotate array using recursion in Java
BlockSwapRecursion.java
public class BlockSwapRecursion
{
public void leftR ( int a [ ] , int p , int q )
{
leftRecursive ( a , 0, p , q ) ;
}
public void leftRecursive ( int in [ ] , int j , int p , int q )
{
if ( p == 0 || p == q )
{
return;
}
if ( q - p == p )
{
swap ( in , j , q - p + j, p ) ;
return;
}
if ( p < q - p )
{
swap ( in , j , q - p + j, p ) ;
leftRecursive ( in , j , p, q - p ) ;
}
else
{
swap ( in , j , p , q - p ) ;
leftRecursive ( in , q - p + j , 2 * q - p , p ) ;
}
}
public void swap ( int in [ ] , int f , int g , int r )
{
int k ;
int temp ;
for ( k = 0 ; k < r ; k++ )
{
temp = in [ f + k ] ;
in [ f + k ] = in [ g + k ] ;
in [ g + k ] = temp ;
}
}
public static void main (String[] argvs)
{
BlockSwapRecursion o1 = new BlockSwapRecursion ();
int a [ ] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,9 } ;
int s = a.length;
int r = 3;
System . out . println ( " Input array " ) ;
for ( int j = 0 ; j < s ; j++ )
{
System . out . print ( a [ j ] + " " ) ;
}
System . out . println ( ) ;
System . out . println ( " The new array after rotating " + r + " times , we get " ) ;
o1 . leftR ( a , r , s ) ;
for( int k = 0 ; k < s ; k++ )
{
System . out . print ( a [ k ] + " " ) ;
}
System . out . println ( " \n " ) ;
// 2nd input
int a1[] = {76 , 18 , 98 , 59 , 30 , 75 , 0 , 87 , 43 , 77 } ;
s = a1 . length ;
r = 5 ;
System . out . println ( " The input array " ) ;
for ( int k = 0 ; k < s ; k++ )
{
System . out . print ( a1 [ k ] + " " ) ;
}
System . out . println ( ) ;
System . out . println ( " The new array after rotating " + r + " times , we get " ) ;
o1 . leftR ( a1 , r , s ) ;
for ( int k = 0 ; k < s ; k++ )
{
System . out . print ( a1 [ k ] + " " ) ;
}
}
} Output
Using Iteration
BlockSwapIteration.java
// Main class of the program
// public class with name
public class BlockSwapIteration
{
// The array's components are rotated by r.
public void left ( int in [ ] , int r , int l )
{
int i , j ;
// if number of time rotating the array is 0 or equal to length of the array return the original array as it is the same
if(r == 0 || r == l)
{
// returning original array
return;
}
// If the array size is greater than the number of elements that need to be rotated
if(r > l)
{
r = r % l;
}
i = r;
j = l - r;
// using while loop to iterate through the array
while (i != j)
{
if(i < j)
{
// using swap functions to swap between the elements of the array
swap ( in, r - i, r + j - i , i ) ;
j = j - i ;
}
else
{
// using swap functions to swap between the elements of the array
swap ( in , r - i , r , j ) ;
i = i - j ;
}
}
swap(in , r - i , r , i ) ;
}
// The procedure replaces the r elements starting at index f with r elements starting at index g.
// swap function to swap elements
public void swap ( int in [ ] , int f , int g , int r )
{
// declaring two integer variables k and temp
// k is used to traverse the array
int k ;
// temp is used in swapping the numbers
int temp ;
// swap algorithm
for ( k = 0 ; k < r ; k++ )
{
temp = in [ f + k ] ;
in [ f + k ] = in [ g + k ] ;
in [ g + k ] = temp ;
}
}
// main method where execution of the program starts
public static void main ( String [ ] args )
{
// creating an object for the Main class
BlockSwapIteration o1 = new BlockSwapIteration ( ) ;
// 1 st input
int a [ ] = { 17 , 29 , 85 , 10 , 45 , 71 , 26 , 48 } ;
// finding the length of the array using length predefined method
int l = a . length ;
// number of times the array need to be rotated
System . out . println ( " Number of times array need to be rotated ") ;
int r = 3 ;
System . out . println ( " The input array: " ) ;
// printing the input array
for ( int i = 0 ; i < l ; i++ )
{
System . out . print ( a [ i ] + " " ) ;
}
System . out . println ( ) ;
// printing the modifid rotated array
System . out . println ( " New array after rotating " + r + " time " ) ;
// calling the left method using object created
o1 . left ( a, r, l ) ;
for ( int i = 0 ; i < l ; i++ )
{
System . out . print ( a [ i ] + " " ) ;
}
System . out . println ( " \n " ) ;
// 2 nd input
int a1 [ ] = { 26 , 18 , 27 , 39 , 10 , 25 , 51 , 63 , 92 , 34 } ;
l = a1 . length ;
r = 4 ;
System . out . println ( " Input array: " ) ;
for ( int i = 0 ; i < l ; i++ )
{
System . out . print ( a1 [ i ] + " " ) ;
}
System . out . println ( ) ;
System . out . println ( " New array after rotating " + r + " times " ) ;
o1 . left (a1, r, l) ;
for ( int i = 0 ; i < l ; i++ )
{
System . out . print ( a1 [ i ] + " " ) ;
}
}
}
Output:
