# Selection

Selection finds the *kth smallest element* of a list of numbers. This algorithm
is often used to find the median (\(k = \lfloor |S|/2 \rfloor\)). Information on
this page is taken from *Algorithms* by Dasgupta et al.

Selection may be implemented with divide-and-conquer. For any number \(v\), imagine splitting list \(S\) into three categories: elements smaller than \(v\), those equal to \(v\), and those greater than \(v\). For example, if array

[2, 36, 5, 21, 8, 13, 11, 20, 5, 4, 1]

is split on \(v = 5\), the three subarrays (\(S_L\), \(S_v\), \(S_R\)) generated are

[2, 4, 1], [5, 5], [36, 21, 8, 13, 11, 20]

The search can instantly be narrowed down to one of these sublists. If we want,
say, the *eighth*-smallest element of \(S\), we know it must be the
*third*-smallest element of \(S_R\) since \(|S_L| + |S_v| = 5\). That is,
selection(\(S\), 8) = selection(\(S_R\), 3). We then recurse on the appropriate
sublist.

The three sublists can be computed in-place with linear time. With poor pivot choice the algorithm is \(O(n^2)\) (worse case). However, on average, the algorithm is \(O(n)\). Like quicksort, random pivot choice usually works well.