[erlang-questions] Priority queues and Erlang

Benjamin Johnston johnston@REDACTED
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 mailing list