## [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.
>>snip
>>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?

Greetings,
Manuel

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