Re: [stella] Bubble Sort II

Subject: Re: [stella] Bubble Sort II
From: Thomas Jentzsch <tjentzsch@xxxxxx>
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 

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

Archives (includes files) at
Unsub & more at

Current Thread