3 ms·

I'm not saying QuickSelect has a large constant. I am saying the median of median O(n) algorithm, which again is not QuickSelect, has a large constant.

• btilly 9y ago
  And I am saying that when you combine the two you get an algorithm with a small constant in practice and guaranteed O(n) behavior in the worst case. For example do quickselect on 9/10 rounds but on every 10th round do a median of medians. The overhead of guaranteed performance will only be a few percent off of the average.
  • lmartel 9y ago
    This didn't make intuitive sense to me so tried to Google it. Is "Introselect" what you're referring to? https://en.wikipedia.org/wiki/Introselect https://en.wikipedia.org/wiki/Introselect It's a hybrid of quickselect and median of medians, but the switching strategy's a bit more complicated.
    • btilly 9y ago
      Introselect is a more complex version of the same idea. But basically both quickselect and median of medians are divide and conquer. Median of medians is an expensive way to guarantee a good division. Quickselect hopes for one. If quickselect goes well, then median of medians will be relatively cheap when run because it is run on a much shorter list. If quickselect does not go well, the median of medians passes guarantee progress. So average behavior is only slightly worse, and worst case behavior is still nicely bounded (albeit with a much worse constant).
  • mabbo 9y ago
    That's very cool. However, the anecdote I was sharing for comparison purposes specially referred to the median of median algorithms. This was also many years ago, long before the paper above was written. I'm not saying that it's impossible to do it and always will be. Re-read what I've said if you like, and you'll see I am simply sharing an anecdote for the purposes of an analogy about this particular situation.