Quickselect Algorithm

Quickselect is a selection algorithm to find the kth smallest element in an unordered list. It is closely related to the quicksort sorting algorithm. Like quicksort, it is efficient in practice and has good average-case performance, but has poor worst-case performance.

 

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

Output: k’th smallest element in the array is 4
 

Input: arr = [7, 4, 6, 3, 9, 1]
k = 0 (k starts from 0)

Output: k’th smallest element in the array is 1

 

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

 
C implementation –
 

Download   Run Code

Output:

K’th smallest element is 4

 

It is worth noticing the resemblance to quicksort algorithm. This simple procedure has expected linear performance, and, like quicksort, has quite good performance in practice 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 eliminating the tail recursion with a loop –
 

 

Time complexity –

Like quicksort, the quickselect has good average performance, but is sensitive to the pivot that is chosen. If good pivots are chosen, meaning ones that consistently decrease the search set by a given fraction, then the search set decreases in size exponentially and by induction (or summing the geometric series) one sees that performance is linear, as each step is linear and the overall time is a constant times this (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). This occurs for example 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. The prototype of std::nth_element is –

void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

 
It rearranges the elements in the range [first,last), in such a way that the element at the nth position is the element that would be in that position in a sorted sequence.

std::nth_element 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++ implementation –
 

Download   Run Code

Output:

K’th smallest element is 4

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

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
nilesh
nilesh

nice algorithm..

cristiancavalli
cristiancavalli

A JS implementation for fun [tests-not-yet-implemented]:
https://github.com/cristiancavalli/quick-select

wpDiscuz