## Re: [stella] Bubble Sort II

 Subject: Re: [stella] Bubble Sort II From: Thomas Jentzsch Date: Tue, 26 Mar 2002 11:13:53 +0100
```Manuel wrote:
>Counting backwards is quicker.

That's true! :-)

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

Where did you get the (n-1)^2 from? Bubble Sort needs n*(n-1)/2
compares.

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

Yes, you need one less compares with each loop. But NO, they
don't run synchronized, because you have to change the stop and
not the start position of the inner loop.

Here's an example again (sorted value a prefixed with *:
0   1   2   3
----------------
11  22  33  44
*44  11  22  33
*44 *33  11  22
*44 *33 *22  11

The inner loop always starts at 2 and is counting down to 0, 1
and 2. The outer loop starts at 0 and is counting up to 2.

Ok, you could let the outer loop go from 2 to 0 (or 3 to 1),
but then you'd have to *calculate* the stop position for the
inner loop.

Have fun!
Thomas

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

```
Current Thread