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(n^{2}).

**C implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include <stdio.h> #define SWAP(x, y) { int temp = x; x = y; y = temp; } #define N (sizeof(A)/sizeof(A[0])) // Partition using Lomuto partition scheme int partition(int a[], int left, int right, int pivotIndex) { // Pick pivotIndex as pivot from the array int pivot = a[pivotIndex]; // Move pivot to end SWAP(a[pivotIndex], a[right]); // elements less than pivot will be pushed to the left of pIndex // elements more than pivot will be pushed to the right of pIndex // equal elements can go either way int pIndex = left; int i; // each time we finds an element less than or equal to pivot, pIndex // is incremented and that element would be placed before the pivot. for (i = left; i < right; i++) { if (a[i] <= pivot) { SWAP(a[i], a[pIndex]); pIndex++; } } // Move pivot to its final place SWAP(a[pIndex], a[right]); // return pIndex (index of pivot element) return pIndex; } // Returns the k-th smallest element of list within left..right // (i.e. left <= k <= right). The search space within the array is // changing for each round - but the list is still the same size. // Thus, k does not need to be updated with each round. int quickselect(int A[], int left, int right, int k) { // If the array contains only one element, return that element if (left == right) return A[left]; // select a pivotIndex between left and right int pivotIndex = left + rand() % (right - left + 1); pivotIndex = partition(A, left, right, pivotIndex); // The pivot is in its final sorted position if (k == pivotIndex) return A[k]; // if k is less than the pivot index else if (k < pivotIndex) return quickselect(A, left, pivotIndex - 1, k); // if k is more than the pivot index else return quickselect(A, pivotIndex + 1, right, k); } // main function int main() { int A[] = { 7, 4, 6, 3, 9, 1 }; int k = 2; printf("K'th smallest element is %d", quickselect(A, 0, N - 1, k)); return 0; } |

**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 –

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Returns the k-th smallest element of list within left..right (inclusive) int quickselect(int A[], int left, int right, int k) { while (1) { // If the array contains only one element, return that element if (left == right) return A[left]; // select a pivotIndex between left and right int pivotIndex = left + rand() % (right - left + 1); pivotIndex = partition(A, left, right, pivotIndex); // The pivot is in its final sorted position if (k == pivotIndex) return A[k]; // if k is less than the pivot index else if (k < pivotIndex) right = pivotIndex - 1; // if k is more than the pivot index else left = pivotIndex + 1; } } |

##### 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(n^{2}). 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 –

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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <iostream> #include <vector> #include <algorithm> // main function int main() { std::vector<int> a = { 7, 4, 6, 3, 9, 1 }; const std::size_t k = 2; std::nth_element(a.begin(), a.begin() + k, a.end()); std::cout << "K'th smallest element is " << a[k]; return 0; } |

**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

nice algorithm..