Selection Problem

• Selecting the $i$th 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.