Array Shuffle | 8 BIT AVENUE

Array Shuffle | 8 BIT AVENUE
Given an array of 2n integers in the following format a1 a2 a3 ... an b1 b2 b3 ... bn. Rearrange the array as follows a1 b1 a2 b2 a3 b3 ... an bn taking into consideration the following restrictions:
1. Arrange the array in place i.e. do not use any additional array
2. Time complexity of the algorithm must be better than O(N2)

A better solution of time complexity O(nlogn) can be achieved using Divide and Concur technique. Let us take an example

1. Start with the array: a1 a2 a3 a4 b1 b2 b3 b4
2. Split the array into two halves: a1 a2 a3 a4 : b1 b2 b3 b4
2. Exchange elements around the center: exchange a3 a4 with b1 b2 you get: a1 a2 b1 b2 a3 a4 b3 b4
3. Split a1 a2 b1 b2 into a1 a2 : b1 b2 then split a3 a4 b3 b4 into a3 a4 : b3 b4
4. Exchange elements around the center for each subarray you get: a1 b1 a2 b2 and a3 b3 a4 b4

Please note that this solution only handles the case when n = 2^i where i = 0, 1, 2, 3 etc.

1.     //l and r are left and right array indexes  
2.     public static void Arrange(int A[], int l, int r)  
3.     {  
4.           
5.         //Base case when the array has only one element  
6.         if (l == r) return;  
7.    
8.         //Array center  
9.         int c = (l + r)/2;  
10.              
11.         int q = 1 + (l + c)/2;  
12.    
13.         //Swap elements around the center  
14.         for (int k = 1, i = q; i <= c; i++, k++)  
15.         {  
16.             int tmp = A[i];  
17.             A[i] = A[c + k];  
18.             A[c + k] = tmp;  
19.         }  
20.    
21.         //Recursively call the function on the left   
22.         //and right halves of the array  
23.         Arrange(A, l, c);  
24.         Arrange(A, c + 1, r);  
25.     } 

X. Brute Force - O(n^2)
A brute force solution involves two nested loops to rotate the elements in the second half of the array to the left. The first loop runs n times to cover all elements in the second half of the array. The second loop rotates the elements to the left. 

1.      public static void main(String[] args)   
2.      {  
3.           int n = 4;  
4.             
5.           int A[] = {1,3,5,7,2,4,6,8};  
6.             
7.           //First loop indexed by i goes from 0 to n-1  
8.           //Second loop changes its start index depending on  
9.           //which element we need to rotate to the left side  
10.           //The number of times the second loop executes is  
11.           //decreased by one for every element we rotate to  
12.           //the left side of the array  
13.           for (int i = 0, q =1, k = n; i < n; i++, k++, q++)  
14.            {  
15.                 for (int j = k; j > i + q; j--)  
16.                {     
17.                     int tmp = A[j-1];  
18.                     A[j-1] = A[j];  
19.                     A[j] = tmp;                      
20.                }  
21.           }  
22.             
23.           for (int i = 0; i  < 2*n; i++) System.out.println(A[i]);  
24.       } 

https://effprog.wordpress.com/2010/08/02/in-a-given-array-of-elements-like-a1-a2-a3-a4-an-b1-b2-b3-b4-bn-c1-c2-c3-c4-cn-without-taking-a-extra-memory-how-to-merge-like-a1-b1-c1-a2-b2-c2-a3-b3-c/
In a given array of elements like [a1, a2, a3, a4, ….. an, b1, b2, b3, b4, ……. bn, c1, c2, c3, c4, …….. cn] without taking a extra memory how to merge like [a1, b1, c1, a2, b2, c2, a3, b3, c3, ………… an, bn, cn]

    if(n > 0 && n % 3 == 0)
        arrange(a, n/3, n/3);

void arrange(int arr[], int n, int i)
{
    if(i == 1)
    {   
        arr[1] = arr[n];
        arr[2] = arr[n << 1]; 
        return;
    }   
    int j = i - 1;

    int c = arr[(n << 1) + j];
    int b = arr[n + j];
    int a = arr[j]; 

    arrange(arr, n, j);

    int x = 3  * j;
    arr[x] = a;
    arr[x + 1] = b;;
    arr[x + 2] = c;
}

http://www.ardendertat.com/2011/10/18/programming-interview-questions-9-convert-array/

Given an array:

convert it to:

This is a tricky question because we could solve it pretty easily if were allowed to construct a new array. The element at the ith position in the final array is at position (i%3)*N + i/3 in the original array. So, the code is simply:

def getIndex(currentIndex, N): return (currentIndex%3)*N + (currentIndex/3)   def convertArray_extraSpace(arr): N=len(arr)/3 return [arr[getIndex(i, N)] for i in range(len(arr))]

However, we aren’t allowed use extra space, we should instead modify the array in-place. We could use a similar approach though, at each iteration we can put the ith element to its final location using the getIndex function above and swap elements. The algorithm works as follows, at each iteration (currentIndex) we get the index of the item that should appear at that location (swapIndex) by calling the getIndex function. The element at swapIndex is the final element to appear at currentIndex. So we swap the elements at currentIndex and swapIndex, if swapIndex>=currentIndex. But if swapIndex<currentIndex then it means that the element at swapIndex was replaced with another element at previous iterations. Now it’s somewhere else and we should keep looking for that element. We again call getIndex with swapIndex as new input to find the element it was replaced with. If the new swapIndex>=currentIndex, we swap the elements as before. Otherwise, we repeat this procedure until swapIndex>=currentIndex, which is we find the final element that’s supposed to appear at currentIndex. The code will make everything clear:

def convertArray(arr): N=len(arr)/3 for currentIndex in range(len(arr)): swapIndex=getIndex(currentIndex, N) while swapIndex<currentIndex: swapIndex=getIndex(swapIndex, N) arr[currentIndex], arr[swapIndex] = arr[swapIndex], arr[currentIndex]

Read full article from Array Shuffle | 8 BIT AVENUE