Selection Algorithms

Algorithms that find the k-th smallest item in a list, such as the median, without sorting the whole list. Quickselect partitions the list in the way quicksort does but follows only the side that holds the wanted position, and introselect combines it with a guaranteed fallback so that the worst case stays fast. They are used wherever a program needs a middle or extreme value of a large set of numbers.