The only way of making quicksort’s worst-case runtime O(n log n) is by limiting recursion depth, as done e.g. in introsort. But that’s no longer quicksort.
The only way of making quicksort’s worst-case runtime O(n log n) is by limiting recursion depth, as done e.g. in introsort. But that’s no longer quicksort.
Quickselect requires a pivot choosing strategy; the problem is not only the same as quicksort's, it is the problem from quicksort.
According to Wikipedia, in the worst case, it is O(n²).[1] But that's not strictly correct, IMO. Regardless, it doesn't answer the OP's question of "is there a selection algorithm that operates in worst case O(n)"
[1]: https://en.wikipedia.org/wiki/Quickselect
[2]: https://news.ycombinator.com/item?id=17888755 and the parent comment; specifically, the median-of-medians algorithm is a worst-case O(n) selection algorithm.
See https://en.m.wikipedia.org/wiki/Quicksort, section "Selection-based pivoting".
https://en.wikipedia.org/wiki/Quicksort#Selection-based_pivo...
> 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.