3 ms·
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 algorit
by ggchappell 13y ago
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?
- eru 13y agoSorry, 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.