QuickSelect

In computer science, quickselect is a selection algorithm to find the $k$th smallest element in an unordered list. It is related to the quicksort sorting algorithm. Like quicksort, it was developed by Tony Hoare, and this is also known as Hoare's selection algorithm. Like quicksort, it is efficient in practice and has good average-case performance but poor worst-case performance. Quickselect and its variants are the selection algorithms most often used in efficient real-world implementations. Quickselect