News for hackers. Stuff that matters.
Re:Helping a stranger, and why you should understand NP-comp... by eru on Monday November 04, 2013 @02:08PM (#6670464)
Introsort is good in practice, but it's not a quicksort.

If you are interested in theory, the pivot in linear time algorithm (like QuickSelect) is truly marvelous. It also provides a good study of how simple a randomized algorithm can be, and how to de-randomize it into something much more complicated but deterministic. But in some sense that complications help you understand, because otherwise, randomize algorithms are often `magic'.

Re:Helping a stranger, and why you should understand NP-comp... by ggchappell on Monday November 04, 2013 @05:02PM (#6671498)
I'm familiar with the median-of-medians linear-time selection algorithm (a.k.a. BFPRT). But I don't recall ever seeing a construction of a pivot-finding algorithm using de-randomization. Do you have a reference for this?
Re:Helping a stranger, and why you should understand NP-comp... by eru on Tuesday November 05, 2013 @12:15AM (#6673353)
Sorry, that was from memory. (Can't you interpret the BFPRT as a de-randomization?)

Anyway, slightly modified my point still stands: BFPRT is way more complicated (and harder to come up with) than randomized QuickSelect.