Arrays1

Q1. Suppose we have an array a1, a2, ..., an, b1, b2, ..., bn. Implement an algorithm to change this array to a1, b1, a2, b2, ..., an, bn without using extra space.

Answer:

public class Arrays1 {
    public void shuffleArray(int[] a) {
        int n = a.length / 2;

        for (int i = 0, j = 1; i < n; i++, j += 2) {
            // right rotate sub-array arr[j] to arr[N+i]
            rightRotate(a, j, n + i);
        }
    }

    // rotate right an array
    private void rightRotate(int[] a, int first, int last) {
        int lastItem = a[last];
        for (int i = last; i > first; i--) {
            a[i] = a[i - 1];
        }
        a[first] = lastItem;
    }

    public void shuffleArrayRecursive(int[] a) {
        shuffleArrayRecursive(a, 0, a.length - 1);
    }

    private void shuffleArrayRecursive(int[] a, int p, int q) {
        if (p == q) {
            return;
        }

        int r = (p + q) / 2;
        swap(a, (p + r) / 2 + 1, r, r + 1, (r + q) / 2);
        shuffleArrayRecursive(a, p, r);
        shuffleArrayRecursive(a, r + 1, q);
    }

    // swap elements from p to q with elements from r to s
    private void swap(int[] a, int p, int q, int r, int s) {
        for (int i1 = p, i2 = r; i1 <= q; i1++, i2++) {
            int temp = a[i1];
            a[i1] = a[i2];
            a[i2] = temp;
        }

    }

    public void printArray(int[] a) {
        System.out.println();
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public static void main(String[] args) {
        Arrays1 obj = new Arrays1();
        int[] a = { 1, 3, 5, 2, 4, 6 };
        obj.printArray(a);
        obj.shuffleArray(a);
        obj.printArray(a);

        int[] b = { 1, 3, 5, 7, 2, 4, 6, 8 };
        obj.printArray(b);
        obj.shuffleArrayRecursive(b);
        obj.printArray(b);
    }
}

• Recursive solution is working correctly only if n is even.
• Order of complexity for rotate function = O(n²)
• Order of complexity for recursive function = O(nlogn)