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