[erlang-questions] Priority queues and Erlang
Mon Jun 15 10:27:43 CEST 2009
>>I have done extensive benchmarking of many kinds of sorts,
>>INCLUDING on small arrays up to size 50. Bubble sort never ever
>>came out on top.
>Well, then either you had a poor implementation or a poor benchmark.
>I'm not sure what to tell you.
>I mean, Abrash is crazy smart. He wouldn't have put it in as the
>culling algorithm for faces in Quake if he hadn't benchmarked the
>silly bejesus out of it.
I suspect the real situation is that Abrash only used the bubble sort on
data that was already sorted or just a swap or two away from being
sorted. I guess such sort problems are common in graphics programming
where not all that much changes between frames, except for a swap here
and there as objects slightly change their relative ordering with
gradual changes in perspective.
I haven't done the sorting benchmarks myself, but I'd definitely trust
Richard here for the general case; much more than I'd generalize from
Abrash's results where he can exploit the particulars of his problem
domain (i.e., bubble sort being generally slow in the worst and average
case, but has a good best-case if it matches the data)
More information about the erlang-questions