## [stella] Bubble Sort II

 Subject: [stella] Bubble Sort II From: cybergoth@xxxxxxxx Date: Tue, 26 Mar 2002 10:02:54 +0100 (CET)
```Hi there!

Thomas wrote:
> BUT, both algorithms won't work, because inner and outer loop
> must go in *opposite* directions.

Now, that didn't let me sleep :-)

Actually it doesn't matter which direction the outer loop goes.
It's just counting the iterations, so whether you start with 0 and
stop with 4 or vice versa doesn't matter.

Except:

Counting backwards is quicker.

And:

Nnow I can initialize the innerloop with the outer index.
That way I do (1+2+3+...+n) compariosions only instead
of the usual (n-1)^2. That way it should be almost as quick as
an insertion sort in the worst case.

An example:

You sort:
12,45,11,5
from biggest to smallest.
Now after the first iteration with three compares,
it looks like this:
45,12,11,5
Now for the second iteration you don't need
to do three compares, since you now know,
that the leftmost value already _must_ be the biggest
you need to do ony 2 compares.

So you need 3-2-1-0 compares to sort the sequence.
What I do know is counting the outer loop 3-2-1-0 too :-)

So you see they're running perfectly synchronized,
not in opposite directions. And it works way fast.

Greetings,
Manuel

-----------------------------------------------------------------------
Riester-Rente - Kassieren Sie das Geld vom Staat:
Zum Förderungsrechner! http://www.arcor.de/home/redir.php/riesterrente
-----------------------------------------------------------------------

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

```