[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.


Counting backwards is quicker.


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:
from biggest to smallest.
Now after the first iteration with three compares, 
it looks like this:
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.


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/

Current Thread