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/
