2 ms·
This is wrong. See https://en.m.wikipedia.org/wiki/Quicksort https://en.m.wikipedia.org/wiki/Quicksort, section "Selection-based pivoting".
by nh2 8y ago
This is wrong.
See https://en.m.wikipedia.org/wiki/Quicksort https://en.m.wikipedia.org/wiki/Quicksort, section "Selection-based pivoting".
- jwilk 8y agoNon-mobile link: https://en.wikipedia.org/wiki/Quicksort#Selection-based_pivoting https://en.wikipedia.org/wiki/Quicksort#Selection-based_pivo...
- deathanatos 8y agoSpecifically, > A variant of quickselect, the median of medians algorithm, chooses pivots more carefully, ensuring that the pivots are near the middle of the data (between the 30th and 70th percentiles), and thus has guaranteed linear time – O(n). This same pivot strategy can be used to construct a variant of quicksort (median of medians quicksort) with O(n log n) time. However, the overhead of choosing the pivot is significant, so this is generally not used in practice.