4 ms·
Isn't there a linear time median selection algorithm, which allows you to always select a pivot in the middle of the sorted part and create two equal halves? Th
by PL_kolek 8y ago
Isn't there a linear time median selection algorithm, which allows you to always select a pivot in the middle of the sorted part and create two equal halves? This produces a worst-case O(n log n) quick sort, which is no longer quick due to the big constant hidden in O notation.
- nh2 8y agoCorrect, Quicksort with Quickselect for pivot choice.
- deathanatos 8y ago"quickselect" is a selection algorithm that uses a partial quicksort in order to do a select. You're essentially saying to write quicksort using 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 https://en.wikipedia.org/wiki/Quickselect [2]: https://news.ycombinator.com/item?id=17888755 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.