Aw: Re: [stella] Star Fire: Getting Closer: Perfect Sorting solution

Subject: Aw: Re: [stella] Star Fire: Getting Closer: Perfect Sorting solution
From: Thomas Jentzsch <tjentzsch@xxxxxx>
Date: Thu, 28 Mar 2002 12:11:03 +0100
Manuel wrote::
>Tada: ->Even though the routine was buggy, it constantly
>        _improved_ the sorting!

Nice idea. :-)

>By running two times, the algorithm can correct
>2 swaps per frame and it is very unlikely, that
>there's more elements swapping at once.

It can do even more, it depends on where the swap happened.

If the inner loop is running up, *all* objects, that are below 
their correct position will "bubble" up. The objects that are 
above their correct position will go down only one position 
every outer loop. So the correct sorting depends on the y-
direction the objects are moving.

>But that fits perfect for Star Fire, I think 8 objects are
>already almost too much onscreen at once.
>- 2*(n-1) compares
>- 2*(n-1) is the maximum of swaps, too

So you get 2*(8-1) = 14 compares/max. swaps vs. 8*(8-1)/2 = 28 
for a complete Bubble Sort and save ~50% cycles.

>> Looks really good, but sometimes (mainly small) objects 
>> disappear completely (e.g. the red fighter). Is that 
>> intentional?
>Hm... I've yet to analyse that. Do they only disappear 
>when near the top or bottom?
>Or do they disappear, when there's 3 or more 
>objects in line?

No, I couldn't find *any* pattern. I think this is probably a 
side effect of the non-perfect sorting you are doing.

Have fun!	

Archives (includes files) at
Unsub & more at

Current Thread