In computer science, quickselect is a Selection algorithm to find the kth smallest element in an unordered list. It is related to the Quicksort Sorting algorithm.

Algorithm¶

To find the `k`-th smallest element in a `list`:

1. Select a `pivotIndex`
2. `Partition` the `list` around the `pivotIndex`
3. If `Partition(...)` returns `k`: `return list[k]`
4. Else if `Partition(...) < k`: Apply `Quicksort` to the left set
5. Else: Apply `Quicksort` to the right set
``````procedure QuickSort(list, targetIndex) is
procedure Swap(list, indexA, indexB) is
...

procedure Partition(list, leftIndex, rightIndex, pivotIndex) is
pivotValue = list[pivotIndex]
swap list[pivotIndex] and list[rightIndex]

i = leftIndex - 1
for j from leftIndex to rightIndex - 1 do
if list[j] <= pivotValue then
i += 1
swap list[i] and list[j]
i += 1
swap list[i] and list[rightIndex]
return i

procedure QuickSortInner(list, leftIndex, rightIndex, targetIndex) is
pivotIndex = rightIndex
pivotIndex = Partition(list, leftIndex, rightIndex, pivotIndex)

if targetIndex is pivotIndex then
return list[pivotIndex]

if targetIndex < pivotIndex then
return QuickSortInner(list, leftIndex, pivotIndex - 1, targetIndex)

return QuickSortInner(list, pivotIndex + 1, rightIndex, targetIndex)

return QuickSortInner(list, 0, len(list)-1, targetIndex)
``````