Observation:
Following is the sequence of indices which we want to swap:
(2,n+1)
(3,n+1)
(4,n+2)
(5,n+1)
(6,n+3)
(7,n+2)
(8,n+4)
(9,n+3)
Hence, for even indices we swap (k,n + k/2) and for odd indices, we swap(k,
n + k/2-1).
This is O(n). and constant space.
for(k=1;k<=2*n;k++) {
if(k%2==0) {
swap(a[k],a[n+k/2]);
} else {
swap(a[k],a[n+k/2-1]);
}
}
*Done!*
Nikhil Jindal
Delhi College of Engineering
On Sat, Aug 7, 2010 at 10:17 AM, Dave <[email protected]> wrote:
> 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]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
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.
