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
AND the algorithm can recognize perfect sorting (no swaps) and
then stop very early. And bubble-sort saves memory, because you
don't need the link-table.
>Accessing data is way cool, too, this iterates once
>through the sorted(!) list:
Iterating through a sorted list without the additional table is
even faster. That helps inside a tight kernel.
Have fun!
Thomas
----------------------------------------------------------------------------------------------
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
