lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


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