Quickselect

Quickselect is a selection algorithm to find the kth smallest element in an unordered list, also known as the kth order statistic. Like the related quicksort sorting algorithm, it was developed by Tony Hoare, and is also known as Hoare's selection algorithm. Quickselect uses the same overall approach as quicksort, choosing one element as a pivot and partitioning the data based on the pivot, but instead of recursing into both sides it only recurses into the side holding the element it is searching for, reducing the average complexity to linear time with a quadratic worst case.