if the array is numbered from 0..(2n-1) i= initial position of int/char f= final position of int/char
if (i < (2n-1)/2) #for integer f = i+i else #for char f = i - ((2n-1)-i) so iterate through the array in the following way choose first element determine it final position put the element in the final position the next element to be processed is the original element in the final position if initial position=final position or the final position was empty,then choose the next element(element next to the initial position) as current element stop when last element has been processed. eg 1234abcd current = 1 i = 0 f = 0+0 = 0 i=f so current= next element= 2 i=1 f=1+1=2 put 2 in 2nd position 1-24abcd current element = original element in 2nd position = 3 for 3 i = 2 f=2+2=4 so put 3 in 4th position 1-243bcd current =a i=4 f=(i - ((2n-1)-i) = (4-(7-4)) = 1 1a243bcd now final position was empty so next element = intital position +1 = intitial position of a +1 = 4 +1 = 5 current = b processing in a similar way 1a2b3-cd current = 4 1a2b3-4d current = c 1a2b3c4d current = d 1a2b3c4d processed last element so stop On Sat, Aug 7, 2010 at 8:02 PM, Ravinder Kumar <[email protected]> wrote: > @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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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.
