C++ Reference ยท Algorithms
The C++ std::nth_element algorithm
Reference for std::nth_element: partially order a range so the element at position n is where it would be if sorted, with examples for median and top-k.
std::nth_element (header <algorithm>) solves the selection problem: it rearranges a range so that the element at position nth is exactly the one that would be there if the whole range were sorted. Everything before nth is not greater than it, everything after is not less. The two sides are not sorted themselves.
Because it does not sort, it runs in linear time on average (O(n)) instead of O(n log n). That makes it the right tool for the median, percentiles, "the k-th smallest" and "the top k in any order". It needs random-access iterators and modifies the range.
std::nth_element(v.begin(), v.begin() + k, v.end()); // v[k] is now the (k+1)-th smallest value
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Syntax
void std::nth_element(RandomIt first, RandomIt nth, RandomIt last); void std::nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp); void std::nth_element(ExecPolicy&& policy, RandomIt first, RandomIt nth, RandomIt last); // C++17 // C++20 std::ranges::nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {});
| Name | Description |
|---|---|
first, last |
The range to rearrange. |
nth |
The position that will hold the value it would have in sorted order. Must be in [first, last]. |
comp |
Strict weak ordering. Default is operator<. |
Returns: void (the ranges version returns an iterator equal to last).
After the call: for every iterator i in [first, nth) and j in [nth, last), comp(*j, *i) is false, so no element on the right is "before" an element on the left. If nth == last, nothing is guaranteed and nothing needs to be done.
Usage notes
- Complexity. Linear on average, O(n). Typically implemented with introselect (quickselect with a fallback), which gives worst-case O(n log n) in libstdc++ but the standard only requires linear on average.
- Neither side is sorted. Print or search the sides only after sorting them. Do not use
binary_searchon the result. - Order of equal elements and the arrangement on each side are unspecified and implementation dependent.
- Median of an even count needs the two middle elements. After
nth_elementat the lower middle, the upper middle is the minimum of the right part, found withmin_element, as in the example. - For top-k with sorted output combine
nth_elementwith asortof the firstkelements, which is O(n + k log k), or usepartial_sort, O(n log k). - It modifies the input. Copy the data first when the original order matters.
- Floating point. Do not use with NaN values:
<is not a strict weak ordering for them and the result is undefined. - Random access only. Lists, sets and other non-random-access containers cannot be used.
- Selection by percentile. For the p-th percentile compute an index
k = (n - 1) * p / 100and callnth_elementat that index; interpolate between neighbors if you need exact statistical definitions.