@Nikhil Jindal check your fromula for indices when k = 3 it is k/2 - 1 = 0 thus it will give swap(3,n).........
On Sat, Aug 7, 2010 at 5:37 PM, Nikhil Jindal <[email protected]>wrote: > 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] > <algogeeks%[email protected]>. > > > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > -- 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.
