News for hackers. Stuff that matters.
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.
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).
Re:Magic: The Gathering Is Turing Complete (2012) by sova on Thursday November 16, 2017 @02:24PM (#15715673)
Wow. can't believe no one ever mentioned this before, Most Significant Bit bucketification would cut down seek time a lot.