## Re: [stella] Bubble Sort

 Subject: Re: [stella] Bubble Sort From: Thomas Jentzsch Date: Tue, 26 Mar 2002 10:45:48 +0100
```Tim wrote:
>The compare is the other way around! You have
>to change the branch condition.

Yup, my fault. No "magic" involved. :-)

Manuel wrote:
>Uhm... won't work?
>
>The one I posted does a perfect job, unlike yours. See
>the demos I attached :-)

I'm still 100% sure that this algorithm will NOT work.

Example: 3 2 1
- tempVar1 starts with 1 (#MAXOBJECTS-2)
- after the first outer loop you get: 1 3 2
- then tempVar1 is decreased to 0
- in the next (and last) outer loop, the inner loop will only
compare 1 and 3, 2 will not be compared again and therefore
should be already correctly sorted, and that's not the case.

Make your demo a little bit slower, then it might be easier to
spot the sorting errors. And with slower movement, it's also
much easier to evaluate flicker.

BTW: This is a simple Bubble Sort (64'er 4/85):
for i = N-1 downto 1
for j = 1 to i
if (y[j] > y[j+1])
swap(y[j], y[j+1])

And here is the optimized Bubble Sort (according to Knuth):
k = N
repeat
i = k-1
k = 0
for j = 1 to i
if (y[j] > y[j+1])
swap(y[j], y[j+1])
k = j
until k = 0

Have fun!
Thomas

----------------------------------------------------------------------------------------------
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/

```