Quickselect

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Quickselect" – news · newspapers · books · scholar · JSTOR (August 2013) (Learn how and when to remove this message)

Quickselect

Animated visualization of the quickselect algorithm. Selecting the 22nd smallest value.
Class	Selection algorithm
Data structure	Array
Worst-case performance	${\displaystyle O}$(n2)
Best-case performance	${\displaystyle O}$(n)
Average performance	${\displaystyle O}$(n)
Optimal	Yes

In computer science, 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 thus is also known as Hoare's selection algorithm.^[1] Like quicksort, it is efficient in practice and has good average-case performance, but has poor worst-case performance. Quickselect and its variants are the selection algorithms most often used in efficient real-world implementations.

Quickselect uses the same overall approach as quicksort, choosing one element as a pivot and partitioning the data in two based on the pivot, accordingly as less than or greater than the pivot. However, instead of recursing into both sides, as in quicksort, quickselect only recurses into one side – the side with the element it is searching for. This reduces the average complexity from ${\displaystyle O(n\log n)}$ to ${\displaystyle O(n)}$, with a worst case of ${\displaystyle O(n^{2})}$.

As with quicksort, quickselect is generally implemented as an in-place algorithm, and beyond selecting the kth element, it also partially sorts the data. See selection algorithm for further discussion of the connection with sorting.