Saturday, October 19, 2013

Alternative arrangement of numbers in the array

Given an array of 2n numbers of the following format
{a1, a2, a3,...an, b1, b2, b3, ...bn}
We have to write a program to transform this into the following format.
{a1, b1, a2, b2, a3, b3, ..., an, bn}

This can be done using the following algorithm. 
We iterate over the array for (n-1) times. In first iteration we swap the middle pair. In the second iteration we swap two of the middle pairs, and so on.

For example let us consider an array of 6 numbers {1,3,5,2,4,6}. Here is how the array is changed while traversing through the algorithm.

1  3  5 <-> 2  4  6
1  3 <-> 2  5 <-> 4  6
1  2  3  4  5  6

Since n = 3, the algorithm iterated just two times and a total of 3 swaps.To generalize, for some arbitrary n, there will be (n2+2*n) / 8 swap operations performed. So it's time complexity is O(n2) and space complexity is O(1).