Re: Speed query

[Frédéric van der Plancke <fvdp@...>]

Geoff Leyland wrote:
> Good question.  I just tested (b) vs a pure lua binary heap and the 
> binary heap is so much better (the sort version still hasn't finished) 
> that I think I must have got (b) wrong 
Well, not necessarily.

On a queue of n items, an insertion or removal costs O(log n) (at worst) 
with a binary heap, O(n log n) (on average) with quicksort. O(x) roughly 
means "proportional to x".

That makes the quicksort implementation about n times slower (x some 
constant value). That factor n may overhelm the advantage of 
quicksorting in C instead of in Lua.

Also, if the quicksort is naively implemented, you may be hitting a 
weakness of the algorithm, such that the sorting time becomes O(n^2) 
instead of O(n log n) : nearly another factor n. (Someone else already 
pointed that out.)

Frédéric