[stella] Sorting Algorithms.

Subject: [stella] Sorting Algorithms.
From: cybergoth@xxxxxxxx
Date: Mon, 25 Mar 2002 10:49:37 +0100 (MET)
Thomas Jentzsch worte:
>Manuel Polik wrote:
>>Here's how I sort the sprites in my intelligent flicker
>>routine. It is adopted from Steve Judds and Pasi Ojalas
>>excellent sorting article in C= Hacking #18.
>>Might this be even quicker than bubble-sort? :-)

>As always: It depends. :-)


>This tree-sorting is WAY faster than bubble-sort for large and
>UNsorted lists: O(n log n) vs O(n^2)

>BUT, in my (and your?) case, the list is not unsorted, but
>imperfect sorted. From frame to frame, the elements move only
>slightly (e.g. +/-1), so 4,5,6,7,8 might become 5,4,5,8,7 or
>3,6,5,6,9 etc. With bubble-sort, this is corrected very soon

Well, unfortunately, I'd have objects appear/disappear any given time,
any place. So a new enemy flying into the scene from top or bottom,
might (depending on the sort order) result in a worst-case Bubble
Sort, from one frame to another!

>AND the algorithm can recognize perfect sorting (no swaps) and
>then stop very early. 

Since I have to cope with a worst case sort any time, any 
early-bail-out-code would only make the situation worse, 
since its overhead would additionally slow down the sort.

>And bubble-sort saves memory, because you
>don't need the link-table.

Hm... even when doing Bubble Sort, I'd 
probably have to sort only links, otherwise
I'd have to swap
Y-Pos/X-Pos/Size/Color/Y-Movment & X-Movement
values on every occuring swap :-)

>Iterating through a sorted list without the additional table is
>even faster. That helps inside a tight kernel.

Well, nothing prevents me from using the links only
temporary for the sorting, then doing all necessary 
swaps _once_ :-)

BTW: Wouldn't you have to support worst-case sort too, 
when switching to the next level?


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