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).
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Created with IntelliJ IDEA. | |
| * User: Ravi | |
| * Date: 10/15/13 | |
| * Time: 7:51 PM | |
| * To change this template use File | Settings | File Templates. | |
| */ | |
| public class ArrangeAlternate { | |
| public static void main( String[] args ) | |
| { | |
| int[] array = {1,3,5,7,2,4,6,8}; | |
| interleave(array); | |
| for( int i = 0; i < array.length; i++ ) | |
| { | |
| System.out.print( array[i] + " "); | |
| } | |
| } | |
| public static void interleave(int[] array) | |
| { | |
| int i = 0; | |
| int j = 0; | |
| int mid = (array.length/2) - 1;//points the end of first half | |
| //the outer loop runs for (length/2) - 1 times | |
| for( i = 0; i < mid ; i++ ) | |
| { | |
| //runs for (i+1) times | |
| for( j = 0; j <= i; j++ ) | |
| { | |
| //calculate the indices to be swapped | |
| int l = mid - i + (2 * j); | |
| int r = mid - i + (2 * j) + 1; | |
| //swap the elements at left (l) and right (r) | |
| int temp = array[l]; | |
| array[l] = array[r]; | |
| array[r] = temp; | |
| } | |
| } | |
| } | |
| } |
by