Monday 18 September 2017

Array Rotation : Block Swap Algorithm

Problem Statement : 
Rotate a given array of integers by K units .

Example

Consider following input array :

A={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}

For a given K=3, the rotated array would look like :

{ 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,1, 2, 3,}

Solution : 
There are a couple of solutions.

1. Take an auxiliary array of size k, copy first k elements into the aux array, shift each element in input array by k units and finally copy aux at last into input array .

2. Block Swap algorithm : This algorithm does'nt require any aux array(extra space) .


Step 1. Divide the array into two parts :
A[0..k-1] A[k...L-1] where L is length
Step 2. Rotate A[0...k-1] keeping the remaining array same.
Step 3 . Rotate A[k....L-1] keeping first part same.
Step 4. Rotate A.


Implementation : 

Here is a simple use case implementation :

package com.grv;

public class ArrayRotation {


    public static void main(String args[]) {


        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};

        int k = 3;
        int l = arr.length;

        arr = swapBlock(arr, 0, k - 1);
        arr = swapBlock(arr, k, l - 1);
        arr = swapBlock(arr, 0, l - 1);


        // print rotated array

        System.out.println("***************************************");
        System.out.println("rotated array is by block swap algo");
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");

    }


    public static int[] swapBlock(int[] a, int start, int end) {


        int i = start;
        int j = end;
        int temp;

        while (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;

            i++;
            j--;

        }


        return a;

    }

}



Test Output: 

*******************************************************
rotated array is by block swap algo
4 5 6 7 8 9 10 11 12 13 14 1 2 3 
Process finished with exit code 0

2 comments:

  1. That's not Block Swap Algorithm. It's called reversal algorithm.
    Block swap algorithm is a different one! Check out here:
    https://www.geeksforgeeks.org/block-swap-algorithm-for-array-rotation/
    https://www.geeksforgeeks.org/program-for-array-rotation-continued-reversal-algorithm/

    ReplyDelete
    Replies
    1. Yeah, that's true. This is not a block swap algorithm

      Delete