4 ms·
Quickselect 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 const
by chowells 9y ago
Quickselect 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.