This article discusses Block Swap Algorithm. It is used to rotate an array by any number of positions with a Time Complexity of O(N) and Space Complexity of O(1).

Table of contents:

1. Problem statement of Array Rotation
2. Block Swap Algorithm
3. Example: Dry Run of Block Swap Algorithm
4. Implementation of Block Swap Algorithm
5. Time Complexity of Block Swap Algorithm
6. Space Complexity of Block Swap Algorithm

Let us get started with Block Swap Algorithm.

Problem statement of Array Rotation

Before we discuss the algorithm, we must take a look at what is actually meant by rotating an array. An array can be rotated by any number of times, in either direction(left or right).

Suppose A = [1,2,3,4,5]

Rotate once to the left: A = [2,3,4,5,1]
Rotate once to the right: A = [5,1,2,3,4]
Rotate by 3 postions to the left: A = [4,5,1,2,3]
Also, note that D rotations to the left are equivalent to N-D rotations to the right.

For, A = [1,2,3,4,5],

Rotate 2 place to the left: A = [3,4,5,1,2].
This is equivalent to 3 rotations to the right (N - D => 5-2 = 3): A = [3,4,5,1,2].

There are a number of ways to rotate an array. Some methods require auxiliary space while others require more than one traversal of the array. However, Block Swap Algorithm provides an efficient way of performing the rotate operation. We shall discuss it in detail in this article.

Reversal Algorithm provides another way of doing the same. Refer this article to gain a good insight on the same.

Block Swap Algorithm

The steps of Block Swap Algorithm are:

1. Divide the array into two parts, A = arr[0...d-1] and B = arr[d...n-1].
2. While size of A is not equal to size of B, do this:
   2.1 If size of A is smaller than B, swap A with a subarray of B of size equal to that of A and which is not adjacent to A.
   2.2 Else(size of B is smaller than A), swap B with a subarray of A of size equal to that of A and which is not adjacent to B.
3. Swap A and B

Let's understand step 2 elaborately:

In 2.1, Size of A is smaller than size of B, so we swap A with a subarray in B such that it is of the same size as A and is not adjacent to A.
For arr = [A][B] and B = [B1][B2] => arr = [A][B1][B2] where size of B2 equals size of A, we swap [A] and [B2] which results in arr = [B2][B1][A]. Now, [A] is in it's correct position. Continue for arr = [B2][B1].

In 2.2, Size of B is smaller than size of A, so we swap B with a subarray in A such that it is of the same size as B and is not adjacent to B.
For arr = [A][B] and A = [A1][A2] => arr = [A1][A2][B] where size of A1 equals size of B, we swap [A1] and [B] which results in arr = [B][A2][A1]. Now, [B] is in it's correct position. Continue for arr = [A2][A1].

Example: Dry Run of Block Swap Algorithm

Consider arr = [1,2,3,4,5], N = 5, d = 2.

Step 1: A = arr[0...1] = [1,2] & B = arr[2...4] = [3,4,5]

Step 2 : As Size(A) < Size(B), swap A with B2 where B2 = [4,5] & B1 = [3]. So, A = [B2] = [4,5] and B = [B1][A] = [3,1,2].

Now, continue for [4,5,3] which corresponds to [B2][B1] as [A] is at it's final position.

So, for the next iteration, the arr is [4,5,3], N = 5, d = 2.
A = arr[0...1] = [4,5] & B = [2...2] = [3]
As Size(A) > Size(B), swap B with a A1 where A1 = [4] & A2 = [5]. So, A1 = [B] = [3] & B = [A1] = 4. And arr = [3,5,4] = [B][A2][A1]

Now, recur for [A2][A1] = [5,4]

So, for this iteration, arr = [5,4], N = 2, d = 2. As, d == N, return the array.

Hence, the resultant array is [3,5,4,1,2] which is also the expected result.

Implementation of Block Swap Algorithm

Following is the Implementation of Block Swap Algorithm in Java:

public static void rotate(int arr[], int i, int d, int n)
{
    if(d == 0 || d == n)
    return;

    if(d == n-d)  //Size of both the arrays is equal
    {
        swap(arr, i, n - d + i, d);   //swap(arr, i, i+d);
        return
    }
    if(d < n-d)
    {
        swap(arr, i, n-d+i, d);
        rotate(arr, i, d, n-d);
    }
    else
    {
        swap(arr, i, d, n-d);
        rotate(arr, n-d+i, 2*d - n,d);
    }
}

 public static void swap(int arr[], int s, int e, int d)
 {
     for(int i=0;i<d;i++)
     {
            int temp = arr[s + i];
            arr[s + i] = arr[e + i];
            arr[e + i] = temp;
     }
 }

Following is the Implementation of Block Swap Algorithm in Java:

void rotate(int arr[], int i, int d, int n)
{
    if(d == 0 || d == n)
    return;

    if(d == n-d)  //Size of both the arrays is equal
    {
        swap(arr, i, n - d + i, d);   //swap(arr, i, i+d);
        return
    }
    if(d < n-d)
    {
        swap(arr, i, n-d+i, d);
        rotate(arr, i, d, n-d);
    }
    else
    {
        swap(arr, i, d, n-d);
        rotate(arr, n-d+i, 2*d - n,d);
    }
}

void swap(int arr[], int s, int e, int d)
{
     for(int i=0;i<d;i++)
     {
            int temp = arr[s + i];
            arr[s + i] = arr[e + i];
            arr[e + i] = temp;
     }
}

Time Complexity of Block Swap Algorithm

This algorithm takes O(N) time.

This is because, for each iteration, we swap d elements, after which d elements come at their correct position. The remaining n-d elements are then passed for the next function call and the same operation is repeated until d becomes equal to n-d. This indicates that the time complexity will be O(N) and that each element will be swapped at least once.

Space Complexity of Block Swap Algorithm

No auxiliary space is used so space complexity of Block Swap Algorithm is O(1).

With this article at OpenGenus, you must have the complete idea of Block Swap Algorithm.