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.