Question

link

We have an array of 2n elements like “a1 a2…an b1 b2…bn”. WAP to rearrange the array as “a1 b1 a2 b2…an bn”

time complexity is O(n) no extra array or memory can be taken.

Input : 1 2 3 4 5 6 7 8 9 10 11 12 (even number input)

Output: 1 7 2 8 3 9 4 10 5 11 6 12

Input : 1 2 3 4 5 6 7 (odd number input)

Output: 1 5 2 6 3 7 4

Analysis

This is a difficult question.

I did not find enough resources online, but have come up with 2 solutions.

Solution

First is like bubble sort (read it somewhere before). Always swap in pairs (starting from the middle): 

1st: 1 2 3 4 5 6 7
2nd: 1 2 3 5 4 6 7
3rd: 1 2 5 3 6 4 7
4th: 1 5 2 6 3 7 4
done

Second solution is to swap in cycles (put current value in its ‘successor’ position, and continue from there). But in order to identify cycles, additional space is used. I wrote the solution making use of ‘visited’ array. The time complexity is between O(n) and O(n^2).

More info on this topic can be found on wikipedia.

Code

written by me

public void rearrange(int[] A) {
    int effLength = A.length;
    if (A.length % 2 == 0) {
        // for even number of input, last element is unchanged
        effLength--;
    }
    // make sure 'effLength' is an odd number.
    int half = effLength / 2 + 1;
    int pos = 1;
    int posValue = A[pos];
    int numSwaps = 0;
    boolean[] visited = new boolean[effLength];
    // visited is used as flag to avoid repeat swap
    // eg. when input is { 1, 2, 3, 4, 5, 6, 7 }, repeat swap as below:
    // 2 -> 3 -> 5 -> 2 -> 3 ...
    while (numSwaps < effLength - 1) {
        // swap (effLength - 1) times because 1st position is unchanged
        int newPos = getNewPosition(A, pos, half);
        if (visited[newPos]) {
            // if this new position is swap already, skip it
            pos = (pos + 1) % effLength;
            posValue = A[pos];
            continue;
        }
        int temp = A[newPos];
        A[newPos] = posValue;
        posValue = temp;
        pos = newPos;

        visited[newPos] = true;
        numSwaps++;
    }
}

private int getNewPosition(int[] array, int pos, int half) {
    if (pos < half) {
        return 2 * pos;
    } else {
        return 2 * (pos - half) + 1;
    }
}