# Quickselect Algorithm Quickselect is a selection algorithm to find the `k'th` smallest element in an unordered list. It is closely related to the Quicksort sorting algorithm. Like Quicksort, it is efficient traditionally and offers good average-case performance, but has a poor worst-case performance.

For example,

Input: [7, 4, 6, 3, 9, 1]
k = 2

Output: k’th smallest array element is 3

Input: [7, 4, 6, 3, 9, 1]
k = 1

Output: k’th smallest array element is 1

Practice this problem

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 recurs into one side with its searching element. Since the pivot is in its final sorted position, all those preceding it in unsorted order, and all those following it in an unsorted order. This reduces the average-case complexity from O(n.log(n)) to O(n) with a worst-case of O(n2), where `n` is the size of the input.

The algorithm can be implemented as follows in C, Java, and Python:

## C

Output:

k’th smallest element is 3

## Java

Output:

k’th smallest element is 3

## Python

Output:

k’th smallest element is 3

It is worth noticing the resemblance to the Quicksort algorithm. This simple procedure has expected linear performance and, like Quicksort, has excellent performance traditionally, and beyond selecting the `k'th` element, it also partially sorts the data. It is also an in-place algorithm, requiring only constant memory overhead if tail-call optimization is available, or we can eliminate the tail recursion with a loop.

Time complexity:

Like Quicksort, the quickselect has good average performance but is sensitive to the chosen pivot. With good pivots, meaning ones that consistently decrease the search set by a given fraction, the search set decreases exponentially. By induction (or summing the geometric series), one sees that performance is linear, as each step is linear. The overall time is constant (depending on how quickly the search set reduces). However, if bad pivots are consistently chosen, such as decreasing by only a single element each time, then worst-case performance is quadratic: O(n2). For example, this occurs in searching for the maximum element of a set, using the first element as the pivot, and having sorted data.

Using `std::nth_element`:

Quickselect and its variants are the selection algorithms most often used in efficient real-world implementations. Quickselect is already provided in the C++ standard library as std::nth_element(first, nth, last) which rearranges the elements in range `[first, last)` so that the item at the `n'th` position is the element that would be in that position in a sorted sequence.

It is typically implemented using a version of quickselect called Introselect. Introselect is a hybrid of quickselect and median of medians. If quickselect takes too long (bad pivot selection), then it falls back to the slower but guaranteed linear time algorithm, thus capping its worst-case runtime before it becomes worse than linear.

## C++

Output:

k’th smallest element is 3

References: https://en.wikipedia.org/wiki/Quickselect

Rate this post

Average rating 4.74/5. Vote count: 196

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Tell us how we can improve this post? 