Algorithm X.1: Finding the median

Input: a list of $n \ge 1$ numbers.
Output: a number.

Determining the median of a collection of data means finding that value such that half the entries are greater than or equal to that value, and half the entries are less than or equal to that value.

The easiest solution is to sort the data and choose the middle value if there are an odd number of entries, and take the average of the two middle entries if there is an even number of values. This, however, is perhaps overkill. Is there a means of finding the median without sorting all the entries?

Algorithm X.2: The selection problem

Input: a list of $n \ge 1$ numbers and an integer $k$ where $1 \le k \le n$.
Output: a number.

A similar problem is, given $n$ objects, what is the $k$^th largest value? Describe an algorithm to find the $k$^th leargest value. This is described as the Selection Problem.

You can read more about this problem at Wikipedia and Steven Skiena's algorithm repository.