Quickselect

Quickselect is a selection algorithm to find the kth smallest element in an unordered list, also known as the kth order statistic.

Learned in CS240.

Best Case: $O(n)$ Average Case: $O(n)$ Worst Case: $O(n^2)$ (? not sure)

https://www.freecodecamp.org/news/quickselect-algorithm-explained-with-examples/

How to choose pivot? I think we just do random index. There’s also median of three. See Quick Sort.

Related

• Quick Sort