Given an array conataing item a1a2a3a4 & b1b2b3b4 reaarange them such as a1b1a2b2a3b3a4b4 & so on

A Naive Attemt:

Algorithm

#include

void swap(char *c,char *p)
{
char tmp;
tmp=*c;
*c=*p;
*p=tmp;

}

int main (int argc, char const* argv[])
{
char str[] = "1234abcd";
int i,j;
int len = strlen(str)/2;
//swap str[len-1] and str[len] and so on
for ( i = 0; i < len-1; i += 1) { for ( j = len-1-i; j <= len+i; j += 2) { printf("i=%d j=%d c1=%c \t c2=%c \n",i,j,str[j],str[j+1]); swap(&str[j],&str[j+1]); } } printf("%s \n", str); return 0; } Time Complexity O(n^2) Space Complexity O(1) An Linear Time Inplace Algorithm Algorithm Step 1) Find an m such that 2m+1 = 3k <= 2n < 3k+1 Step 2) Right cyclic shift A[m+1 ... n+m] by m. Step 3) Foreach i = 0 to k - 1, considering only the Array[1...2m] start at 3i and 'follow the cycle'. Step 4) Recurse on A[2m+1...2n] Basic idea is as follows: If for each n, we can find an m (Step 1) for which we can easily do the 'following the cycle' algorithm, we can first shuffle some elements (Step 2), then do the algo for m (Step 3) and then recurse on the remaining elements (Step 4). 'following the cycle': element i1 goes to i2 which goes to i3 ... goes to finally back to i1. We can put the elements of this cycle in their right places by using just one extra location as follows: Store element i1 in the extra location. Look at what goes into i1. say X1. Store element in X1 in i1. Follow the cycle. Finally store i1 in is right position. #include
#include
#include


void Inshuffle(int *A, int N);
void follow_cycle(int *A, int N, int seed);
void cyclic_shift(int *A, int size, int distance);
void reverse(int *A, int size);
int Inverseof2(int M);


/***************************
Main Insuffle Algorithm.
Shuffle a1 a2 ..an b1 b2 ...bn
to
b1 a1 b2 a2 .... bn an

Parameters: A = the array
N = 2n, size of the array.

The permutation is given by
i -> 2i mod (N + 1)

We shuffle the array starting
from A[1] for easier coding.
****************************/

void Inshuffle(int *initialA, int initialN)
{

int m =1;
int i;
int power3 = 1;
int seed = 1;
int k = 1;
int n = initialN/2; //N is assumed to be even.
int *A = initialA;
int N = initialN;

while (N > 0){


//Reset Values.
m = 1;
i = 0;
power3 = 1;
seed = 1;
k = 1;
n = N/2;

//Step 1: Find an m such that 2m+1 is the largest power of 3 <= N+1 for (i = 0; i <= N+1; i ++){ if (3*power3 > N+1){
break;
}
power3 = 3*power3;
}
k = i;

m = (power3 - 1)/2;
//Step 2: Cyclic Right Shift A[m+1, n+m] by m
cyclic_shift(A+m+1,n,m);

// Step3: Do inshuffle of A[1....2m] by 'following cycle'.

for (i = 0 ; i < k; i ++) { follow_cycle(A,2*m,seed); seed = 3*seed; } // Step 4: Recurse on A[2m+1...,2n] //Could have made a recursive call here: //Inshuffle(A+2*m,2*(n-m)); // But to make it O(1) space, convert tail recursion to iteration and put in a while loop. A = A + 2*m; N = 2*(n-m); // Reset Values. } //End of while loop. } /**************************************** Follow the cycle starting at seed. For example: insuffle of 1 2 3 4 5 6 7 8 1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1
We follow this cycle in reverse order.
We look at 1. Save A[1].
Then look at what goes to 1, i.e 5 = 1*x
where x is inverse of 2.
Now fill A[1] with A[5].
Now look at what goes into A[5]. 7 = 5*x
(x is inverse of 2)
So fill A[5] with A[7].
And so on.
*****************************************/

void follow_cycle(int *A, int N, int seed)
{
int cur;
int inverse2 = Inverseof2(N+1);
int tmp;
int prev;

cur = (seed*inverse2 % (N+1));

tmp = A[seed];
prev = seed;
while (cur != seed){
A[prev] = A[cur];
prev = cur;
cur = (cur*inverse2 % (N+1));
}
A[prev] = tmp;
}
/*******************************
cyclic right shift an array by a given amount.
********************************/
void cyclic_shift(int *A, int sz, int k)
{
reverse(A,sz - k);
reverse(A+sz-k,k);
reverse(A,sz);
}

/******************************
reverse an array
*******************************/
void reverse(int *A, int sz)
{
int i;
int tmp;
for (i = 0; i < sz/2; i++)
{
tmp = A[i];
A[i] = A[sz-i-1];
A[sz-i-1] = tmp;
}
}

/***************************

find x such that 2x = 1 (mod M)
M is assumed to be an odd integer.
x = (M+1)/2
***************************/
int Inverseof2(int M)
{
return (M+1)/2;
}


int main()
{
int n;
int i;
int *A;
printf("Enter the value of n, (total size of array = 2n): ");
scanf("%d",&n);
A = (int *)malloc((2*n+1)*sizeof(int));
for (i = 0; i <= 2*n; i++){
A[i] = i;
}

Inshuffle(A,2*n);

printf("\n[");
for (i = 1; i <= 2*n; i ++){
printf(" %d",A[i]);
}
printf(" ]\n");
free(A);
return 1;
}

Time Complexity O(N)
Space Compleixty O(1)
Run Here https://ideone.com/2yLq1
A Great Source http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi board=riddles_cs;action=display;num=1094241218;