Arranging sequence

Question: we have an array of 2n elements like "a1 a2...an b1 b2...bn". WAP to rearrange the array as "a1 b1 a2 b2...an bn"
time complexity is O(n) no extra array or memory can be taken...

Answer:
I have an answer but could not meet the complexity requirement.

C code:

#include<stdio.h>
#define SWAP(a,b) a^=b^=a^=b

int string[100];
int m;

void Replace(int n,int start){
int i,j;
   for(i=start,j=0;j<n;i++,j++)
{
   SWAP(string[i],string[n+i]);
}
   n=n-1;
   if(n>0)
   Replace(n,start+1);
}

main()
{
int i;
printf("Enter no of elements (max 100): ");
scanf("%d",&m);
if(m%2){
printf("odd nos\n");
}
else{
printf("Enter numbers: ");
for(i=0;i<m;i++)
scanf("%d",&string[i]);
for(i=0;i<m;i++)
printf("%d\t",string[i]);
printf("\n");

Replace(m/2-1,1);
for(i=0;i<m;i++)
printf("%d\t",string[i]);
printf("\n");
}
}

Output:

Enter no of elements (max 100): 12
Enter numbers:
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12
1 7 2 8 3 9 4 10 5 11 6 12

Output with intermediate steps:
Enter no of elements (max 100): 12
Enter numbers:
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12
1 7 8 9 10 11 2 3 4 5 6 12
1 7 2 3 4 5 8 9 10 11 6 12
1 7 2 8 9 10 3 4 5 11 6 12
1 7 2 8 3 4 9 10 5 11 6 12
1 7 2 8 3 9 4 10 5 11 6 12
1 7 2 8 3 9 4 10 5 11 6 12

If you can suggest a better solution, please revert.

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.

5 Comments

Akash

December 1, 2008 at 1:31 PM

I got another efficient solution at http://groups.google.com/group/programming-puzzles/browse_thread/thread/d865eaa36ce863ae/3a5e885accab1f37?lnk=gst&q=shuffle&pli=1 by Dave.

int Shuffle( int a[], int N)

{
int i, j, m, t, u;

if( N < 2 || N%2 != 0 ) return 1;

if( N == 2 ) return 0;

m = N-2;
i = j = 1;
t = a[j];
do
{
j = (j+j < N ? j+j : j+j-N+1);
u = a[j];
a[j] = t;
t = u;
m--;
}
while( j != i );

while( m > 0 )
{
do
{
j = ++i;
do
j = (j+j < N ? j+j : j+j-N+1);
while( j > i );
}
while( j != i );

t = a[j];
do
{
j = (j+j < N ? j+j : j+j-N+1);
u = a[j];
a[j] = t;
t = u;
m--;
}
while( j != i );

}

return 0;
}

Sample run

Enter no of elements (max 100): 12
Enter numbers: 1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12
1 2 2 4 5 6 7 8 9 10 11 12
1 2 2 4 3 6 7 8 9 10 11 12
1 2 2 4 3 6 7 8 5 10 11 12
1 2 2 4 3 9 7 8 5 10 11 12
1 2 2 4 3 9 7 8 5 10 6 12
1 2 2 4 3 9 7 8 5 11 6 12
1 2 2 4 3 9 7 10 5 11 6 12
1 2 2 8 3 9 7 10 5 11 6 12
1 2 2 8 3 9 4 10 5 11 6 12
1 7 2 8 3 9 4 10 5 11 6 12
1 7 2 8 3 9 4 10 5 11 6 12

Unknown

May 24, 2010 at 4:23 PM

What abt this one(JAVA)

public static String converta1a2a3b1b2b3Toa1b1a2b2a3b3(String st) {
char[] car = st.toCharArray();
converta1a2a3b1b2b3Toa1b1a2b2a3b3Helper(car, car.length, 0);
return String.valueOf(car);
}

private static void converta1a2a3b1b2b3Toa1b1a2b2a3b3Helper(char[] car,
int length, int i) {
if (i == length)
return;
if (i < length / 2) {
char temp = car[i];
converta1a2a3b1b2b3Toa1b1a2b2a3b3Helper(car, length, i + 1);
car[2 * i] = temp;
} else {
car[2 * (i - length / 2) + 1] = car[i];
converta1a2a3b1b2b3Toa1b1a2b2a3b3Helper(car, length, i + 1);
}
}

Alyosha

September 27, 2010 at 12:41 PM

How about this?

void shuffle2(int a[], const int size)
{
int curIterBegin = 1;
int countOfSteps = size - 2;
int i = curIterBegin;
int nextToSet = a[i];
while (countOfSteps-- > 0)
{
i = i * 2 % (size - 1);
int setNow = nextToSet;
nextToSet = a[i];
a[i] = setNow;
if (i == curIterBegin)
{
curIterBegin += 2;
i = curIterBegin;
nextToSet = a[i];
}
}
}

Omar Mohammad Othman

April 20, 2012 at 12:26 PM

Take a look at this:

http://arxiv.org/abs/0805.1598

Anonymous

July 19, 2012 at 12:23 PM

int interleave(char* string)
{
int stringLength = strlen(string);

if(stringLength % 2 != 0)
{
printf("ERROR: Array length should not be odd");
return -1;
}

int temp_index = 1;
char temp_value = string[temp_index];
int n = stringLength/2;

do
{
int destination_index = 0;
char destination_value = string[destination_index];

if(temp_index < n)
{
destination_index = 2 * temp_index;
}
else
{
destination_index = 2 * (temp_index - n) + 1;
}

destination_value = string[destination_index];
string[destination_index] = temp_value;

temp_index = destination_index;
temp_value = destination_value;

}while(temp_index != 1);

printf("Interleaved array: %s\n", string);

}

PROGRAMMING INTERVIEWS

Arranging sequence

5 Comments

Find us on Facebook

I write about