4 ms·
This is even more nitpicky, but the worst-case running time can be improved to O(n log n) by choosing the median of the input numbers to be the pivot each time,
by gphilip 13y ago
This is even more nitpicky, but the worst-case running time can be improved to O(n log n) by choosing the median of the input numbers to be the pivot each time, in O(n) time. This works irrespective of whether the list is sorted or not. This is /not/ useful in practice because of the overhead of choosing the pivot this way, but hey, theory is theory!
"... given a worst-case O(n) selection algorithm, one can use it to find the ideal pivot (the median) at every step of quicksort, producing a variant with worst-case O(n log n) running time. In practical implementations this variant is considerably slower on average, but it is of theoretical interest, showing how an optimal selection algorithm can yield an optimal sorting algorithm."
https://en.wikipedia.org/wiki/Quicksort#Selection-based_pivoting https://en.wikipedia.org/wiki/Quicksort#Selection-based_pivo...
- ggchappell 13y agoA better way to improve the worst case to O(n log n) time is to use the "Introsort" optimization.[1] Keep track of the recursion depth (with optimized-out tail-recursive calls counted). If the depth exceeds k * log_2(n) [maybe k = 2?], then switch to Heap Sort for the current sublist. This optimization is useful in practice. The result is a sort that is as fast as Quicksort on average, but unlike Quicksort runs in O(n log n) time. So, for example, the C++ Standard Library function std::sort will use Introsort in any good implementation. Despite its wonderfulness, Introsort is strangely little known. Algorithms texts rarely mention it, for some reason. [1] https://en.wikipedia.org/wiki/Introsort https://en.wikipedia.org/wiki/Introsort
- eru 13y agoIntrosort 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'.
- ggchappell 13y agoI'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.