Arrange Array Elements

In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn].
PS: Do it without using extra memory

Sample Testcases:
Input #00:{1,2,3,4,5,6,7,8,9,10,11,12}
Output #00:{1,5,9,2,6,10,3,7,11,4,8,12}

Explanation:
Here as you can notice, the array is of the form
{a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4}

Related:
http://www.geeksforgeeks.org/an-in-place-algorithm-for-string-transformation/

Variation 1:

I/P:1234abcd  in array

O/P:1a2b3c4d

Method 1:

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))]

The getIndex function takes an index from the final array, and returns the index of the element in the original array that should appear at that position. 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. 

Pseudo Code:

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

The algorithm is pretty simple and in-place without using extra space. 

Let’s work through an example to clarify, here is the program flow for an array of size 15. Swap index is calculated multiple times for some elements until swapIndex>=currentIndex as explained above.

currentIdx=0, swapIdx=0, swapIdx>=currentIdx, swap arr[0] arr[0]
currentIdx=1, swapIdx=5, swapIdx>=currentIdx, swap arr[1] arr[5]
currentIdx=2, swapIdx=10, swapIdx>=currentIdx, swap arr[2] arr[10]
currentIdx=3, swapIdx=1, swapIdx<currentIdx, no swap
  swapIdx=1, newSwapIdx=5, newSwapIdx>=currentIdx, swap arr[3] arr[5]
currentIdx=4, swapIdx=6, swapIdx>=currentIdx, swap arr[4] arr[6]
currentIdx=5, swapIdx=11, swapIdx>=currentIdx, swap arr[5] arr[11]
currentIdx=6, swapIdx=2, swapIdx<currentIdx, no swap
  swapIdx=2, newSwapIdx=10, newSwapIdx>=currentIdx, swap arr[6] arr[10]
currentIdx=7, swapIdx=7, swapIdx>=currentIdx, swap arr[7] arr[7]
currentIdx=8, swapIdx=12, swapIdx>=currentIdx, swap arr[8] arr[12]
currentIdx=9, swapIdx=3, swapIdx<currentIdx, no swap
  swapIdx=3, newSwapIdx=1, newSwapIdx<currentIdx, no swap
  swapIdx=1, newSwapIdx=5, newSwapIdx<currentIdx, no swap
  swapIdx=5, newSwapIdx=11, newSwapIdx>=currentIdx, swap arr[9] arr[11]
currentIdx=10, swapIdx=8, swapIdx<currentIdx, no swap
  swapIdx=8, newSwapIdx=12, newSwapIdx>=currentIdx, swap arr[10] arr[12]
currentIdx=11, swapIdx=13, swapIdx>=currentIdx, swap arr[11] arr[13]
currentIdx=12, swapIdx=4, swapIdx<currentIdx, no swap
  swapIdx=4, newSwapIdx=6, newSwapIdx<currentIdx, no swap
  swapIdx=6, newSwapIdx=2, newSwapIdx<currentIdx, no swap
  swapIdx=2, newSwapIdx=10, newSwapIdx<currentIdx, no swap
  swapIdx=10, newSwapIdx=8, newSwapIdx<currentIdx, no swap  
  swapIdx=8, newSwapIdx=12, newSwapIdx>=currentIdx, swap arr[12] arr[12]
currentIdx=13, swapIdx=9, swapIdx<currentIdx, no swap
  swapIdx=9, newSwapIdx=3, newSwapIdx<currentIdx, no swap
  swapIdx=3, newSwapIdx=1, newSwapIdx<currentIdx, no swap
  swapIdx=1, newSwapIdx=5, newSwapIdx<currentIdx, no swap
  swapIdx=5, newSwapIdx=11, newSwapIdx<currentIdx, no swap
  swapIdx=13, newSwapIdx=13, newSwapIdx>=currentIdx, swap arr[13] arr[13]
currentIdx=14, swapIdx=14, currentIdx>=swapIdx, swap arr[14] arr[14]

The time complexity of this algorithm depends on the number of times getIndex function is called. It’s not linear because for some indexes the getIndex function is called multiple times, it’s not quadratic as well because not for every element the getIndex is called repetitively. We can see both of the cases above. So, the complexity is between linear and quadratic, which is sometimes called as super-linear. To be precise, the complexity is approximately O(N^1.3)
Alternate Solution:
Code:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

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;
}

int main()
{
    int n;
    scanf("%d", &n);

    int a[n], i;
    for(i = 0; i < n; ++i)
        scanf("%d", a + i);

    if(n > 0 && n % 3 == 0)
        arrange(a, n/3, n/3);
 
    for(int i = 0; i < n; ++i)
        printf("%d ", a[i]);
    printf("\n");
    system("pause");
    return 0;
}

Variation 1:

Observation: 

a(i) = where will be placed the i-th initial element, then a(i)=2*i for the first half and a(i)=2*i - N + 1 for the second half.

so start from index 1,
temp=a[1],
a[1]='  ' ,calculate its replacement address,which is pos=2*1=2,
swap(temp,a[pos]) ;
repeat this until temp='  '

Now half of the string is replaced ,now get the next starting index of a to be replaced , i.e where first integer followed by char sequence is flase.
now start above process by making index=now calculated next start address.

Code:

#include <stdio.h>
int getFirstHalfPos(int i) //To return first half replacement address
{
    return 2*i;
}

int getSecondHalfPos(int i,int N) //To return second half replacement address
{
    return (2*i)-N+1;
}
void swap(char *a, char *b)
{
    char temp=*a;
    *a=*b;
    *b=temp;
}

int getNextPos(char a[] ,int N)  //To get next starting address of char to be replaced
{
    int i=0;
    while((a[i]-'0'>=0 && a[i]-'0'<=9) && !(a[i+1]-'0'>=0 && a[i+1]-'0'<=9) && i<N)
    //Until first char is int and second char is charcter ,mov forward
        i=i+2;
    if(i<N)
        return i+1;
    else
        return 0;
   
}
void arrange(char a[], int i,int N)
{
    char temp=a[i];
    int pos;
    a[i]=' ';
    do
    {
    if(i<N/2)
        i=getFirstHalfPos(i);
    else
        i=getSecondHalfPos(i,N);
    swap(&temp,&a[i]);
    }while(temp!=' ');
    pos=getNextPos(a,N);
    if(pos)
    {
            arrange(a,pos,N); //this is just a tail recursion so I can implement it using For loop
    }
}
int main()
{
    char a[]="12345678abcdefgh";
    printf("\nBefore Arrange: %s",a);
    arrange(a,1,sizeof(a)-1); //dont know why my compiler is giving sizeof(a)=17 instead of 16, thats why I deducted 1 from it.
    printf("\nAfter Arrange: %s",a);
    return 0;
}

Time Complexity:O(n) in place