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 -~----------~----~----~----~------~----~------~--~---
