Quick Select

Last updated Dec 27, 2021 Edit Source

• Cs algorithms

Quick Select is an algorithm similar to Quick Sort, except it does not sort a given but finds the nth smallest element in an array in $O(n)$ time. However, this algorithm has a worst case time complexity of $O(n^2)$ since the recursion tree can be imbalanced. Here is the pseudocode for a function that finds the kth smallest element in an array A:

1
2
3
4
5
6
7
8

QuickSelect(n, k):
	Populate L, E, G arrays according to a randomly chosen pivot
	if len(L) >= k:
		return QuickSelect(L,k)
	else if len(L) + len(E) >= k:
		return E[0]
	else:
		return QuickSelect(G,k - (len(L)+len(E))