Re:Magic: The Gathering Is Turing Complete (2012)
by chowells on Thursday November 16, 2017 @11:57AM
(#15714247)
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.
[ Parent
| on HN ]
Re:Magic: The Gathering Is Turing Complete (2012)
by mabbo on Thursday November 16, 2017 @12:05PM
(#15714341)
Yeah, 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.
Re:Magic: The Gathering Is Turing Complete (2012)
by ekelsen on Thursday November 16, 2017 @02:13PM
(#15715562)
If 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).