4 ms·
But the constant is not large. O(n) quickselect is extremely fast algorithm.
by nlperguiy 9y ago
But the constant is not large. O(n) quickselect is extremely fast algorithm.
- mabbo 9y agoOh, you should have seen my implementation then.
- chowells 9y agoQuickselect has an O(n^2) worst case, unless you use a variant like Tarjan's median-of-medians algorithm for selecting the pivot. And that does have awful constant factors.
- mabbo 9y agoYeah, this was the specific algorithm I meant. O(n) time, but in my undergrad implementation, it wasn't useful with less than billions of items, vs just sorting and selecting with highly optimized sorts.
- ekelsen 9y agoIf you are dealing with numbers, then you can do this is true O(n) time with radix-select. (Basically do a MSB radix sort and only do subsequent passes in the bucket where you know k must be).
- sova 9y agoWow. can't believe no one ever mentioned this before, Most Significant Bit bucketification would cut down seek time a lot.