Here's a solution that I am pretty sure is less than O(n^2). The data
are moved only once, but timing the routine suggests that it is O(n
log n), but I have no proof of that.
The first and last do-while loops move cycles of data, while the
nested do-while loops find the beginning index of a new cycle.
Dave
int Shuffle( int a[], int N)
{
int i, j, m, t, u;
if( N < 1 ) return 1;
if( N == 2 ) return 0;
N *= 2;
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;
}
On Aug 6, 12:37 pm, UMESH KUMAR <[email protected]> wrote:
> how to sort specific order the given array ,Without using extra memory
>
> Input:-a1,a2,a3,a4,a5......an,b1,b2,b3,b4,b5..........bn.
>
> output:-a1,b1,a2,b2,a3,b3,........an.bn
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
