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)

Implementation

Bibliography