C++ Standard Library Algorithms Using std::nth_element To Find The Median (Or Other Quantiles)
Example
The std::nth_element algorithm takes three iterators: an iterator to the beginning, nth position, and end. Once the function returns, the nth element (by order) will be the nth smallest element. (The function has more elaborate overloads, e.g., some taking comparison functors; see the above link for all the variations.)
Note This function is very efficient - it has linear complexity.
For the sake of this example, let's define the median of a sequence of length n as the element that would be in position ⌈n / 2⌉. For example, the median of a sequence of length 5 is the 3rd smallest element, and so is the median of a sequence of length 6.
To use this function to find the median, we can use the following. Say we start with
std::vector<int> v{5, 1, 2, 3, 4};
std::vector<int>::iterator b = v.begin();
std::vector<int>::iterator e = v.end();
std::vector<int>::iterator med = b;
std::advance(med, v.size() / 2);
// This makes the 2nd position hold the median.
std::nth_element(b, med, e);
// The median is now at v[2].
To find the pth quantile, we would change some of the lines above:
const std::size_t pos = p * std::distance(b, e);
std::advance(nth, pos);
and look for the quantile at position pos.
