# Selection Problem - Selecting the $i$th [[order-statistics|order statistic]] from $n$ numbers. There are algorithms asymptotically faster than [[sorting]] the array first. - Modeled after [[quicksort]], but only works on one partition, which is an example of [[prune-and-search]] technique, thus the runtime is $\Theta(n)$ instead of $O(n\lg n)$. - Random Selection has a worst case runtime of $\Theta(n^2)$, in the case of finding minimum, as the size of problem is reduced only by $1$ at each partitioning. - Randomized Selection, improved - Dividing into 5-elements groups - Sort each groups - Recursively find the "median of medians" - Use the"median of the medians" as our pivot, so that we are ==guaranteed to eliminate 3/7 of the elements no matter how we partition.== ## Related Problems - Median of two sorted arrays: Find two medians, compare, discard the upper/lower halves accordingly, recurse. - multi-selection problem - Find the middle one of the $k$. - Use selection to find the $k$th element. - Use this element as pivot to partition, so that each partition has half of the $k$s.