#include<stdio.h> main(){ //{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16} int i,a[]={0,1,1,2,2,3,3,4,4,5,5, 6, 6, 7, 7, 8, 8};
int count,temp,value_of_i,m=0; for(i=0;i<16;i++) printf("%d ",i); printf("\n"); for(i=0;i<16;i++) printf("%d ",a[i]); i=2; value_of_i=1; printf("\n"); for(count=0;count<13;count++) { if(i%2==0) { i=7+i/2; temp=a[i]; a[i]=value_of_i; value_of_i=temp; printf("(%d %d) \n ",i,value_of_i); } else { i=(1+i)/2; ; temp=a[i]; a[i]=value_of_i; value_of_i=temp; printf("(%d %d)\n", i,value_of_i); } for(m=1;m<17;m++) printf("%d ",a[m]); } printf("hi"); } On Nov 16, 7:29 pm, "Vikram Venkatesan" <[EMAIL PROTECTED]> wrote: > Hi Ksitami, > In the first algorithm, what if the CYLCE OF REPLACEMENTS sorts the > whole array(I mean, all the elements are visited during the 1st iteration > itself, thus creating a COMPLETE CYCLE of the array, putting it in the right > order), and the array gets to the FINAL position (i.e. a1a2...b1b2...) > before 'i' could reach n/2 ?. > > In that case, won't the REPEAT ..UNTIL block be MODIFYING ELEMENTS THAT HAVE > ALREADY BEEN MOVED TO THEIR CORRECT POSITIONS... > > In general, how can we be sure that 'i' doesn't pick up elements that are > already sorted? (during successive iterations of WHILE, as a result of i += > 2) > > Pls correct me if i am wrong... > > Thanks, > Vikram > > On 11/16/06, Ksitami <[EMAIL PROTECTED]> wrote: > > > > > Idris napisaĆ(a): > > > How about using 1 variable o(1) Space.. > > > > i.e Scan the array and compare the element... at a[1]=a1, a[2]=b1, > > > a[3]=a2,...... > > > > first check(a[i]), say b2 in array of size 8, so Its clear b2 must be > > > placed at 8/2+2 position in an array.. > > > "012345678" => "024681357" > > .------------------------------------------ > > . Idris agorithm > > . SubLinear but not deterministic > > . > > . n2=n div 2 > > . if odd(n) then n2+=1 //n2 first odd > > . i=1 > > . while i<n2 > > . firsti=i > > . x=t[i] > > . if odd(i) > > . then i=i div 2 + n2 > > . else i=i div 2 > > . repeat > > . b=t[i]; t[i]=x; x=b > > . if odd(i) > > . then i:=i div 2 + n2 > > . else i:=i div 2 > > . until firsti=i > > . t[i]=x; lz+=1 > > . i+= 2 * MagicDice // here is magic ;-) > > .------------------------------------------ > > > But, > > .------------------------------------------ > > . // OddSort > > . n2= n div 2 > > . if odd(n) n2++ //extra > > . for j=1 to n2-1 > > . k= j > > . if j>1 > > . repeat > > . k= (k*2) mod (2*n2 - 1); > > . until k<=j > > . if k=j > > . store=t[j] > > . y=j > > . repeat > > . k=y > > . y= (2*k) mod (2*n2 - 1) > > . t[k]= t[y] > > . until y=j > > . t[k]=store > > . from: > > . "A Handbook of Time-Series Analysis, > > . Signal Processing and Dynamics" > > . by D. S. G. Pollock > > .------------------------------------------ --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---