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
:
- Select a
pivotIndex
Partition
thelist
around thepivotIndex
- If
Partition(...)
returnsk
:return list[k]
- Else if
Partition(...) < k
: ApplyQuicksort
to the left set - 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)