# nth_element

Category: algorithms | Component type: function

### Prototype

`Nth_element` is an overloaded name; there are actually two `nth_element` functions.

    template <class RandomAccessIterator>
    void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                     RandomAccessIterator last);

    template <class RandomAccessIterator, class StrictWeakOrdering>
    void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                     RandomAccessIterator last, StrictWeakOrdering comp);

### Description

`Nth_element` is similar to `partial_sort`, in that it partially orders a range of elements: it arranges the range `[first, last)` such that the element pointed to by the iterator `nth` is the same as the element that would be in that position if the entire range `[first, last)` had been sorted. Additionally, none of the elements in the range `[nth, last)` is less than any of the elements in the range `[first, nth)`. [1]

The two versions of `nth_element` differ in how they define whether one element is less than another. The first version compares objects using `operator<`, and the second compares objects using a function object `comp`.

The postcondition for the first version of `nth_element` is as follows. There exists no iterator `i` in the range `[first, nth)` such that `*nth < *i`, and there exists no iterator `j` in the range `[nth + 1, last)` such that `*j < *nth`.

The postcondition for the second version of `nth_element` is as follows. There exists no iterator `i` in the range `[first, nth)` such that `comp(*nth, *i)` is `true`, and there exists no iterator `j` in the range `[nth + 1, last)` such that `comp(*j, *nth)` is `true`.

### Definition

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

### Requirements on types

For the first version, the one that takes three arguments:

- `RandomAccessIterator` is a model of Random Access Iterator.
- `RandomAccessIterator` is mutable.
- `RandomAccessIterator`'s value type is LessThan Comparable.
- The ordering relation on `RandomAccessIterator`'s value type is a strict weak ordering, as defined in the LessThan Comparable requirements.

For the second version, the one that takes four arguments:

- `RandomAccessIterator` is a model of Random Access Iterator.
- `RandomAccessIterator` is mutable.
- `StrictWeakOrdering` is a model of Strict Weak Ordering.
- `RandomAccessIterator`'s value type is convertible to `StrictWeakOrdering`'s argument type.

### Preconditions

- `[first, nth)` is a valid range.
- `[nth, last)` is a valid range.

(It follows from these two conditions that `[first, last)` is a valid range.)

### Complexity

On average, linear in `last - first`. [2]

### Example

    int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
    const int N = sizeof(A) / sizeof(int);

    nth_element(A, A + 6, A + N);
    copy(A, A + N, ostream_iterator<int>(cout, " "));
    // The printed result is "5 2 6 1 4 3 7 8 9 10 11 12".

### Notes

[1] The way in which this differs from `partial_sort` is that neither the range `[first, nth)` nor the range `[nth, last)` is be sorted: it is simply guaranteed that none of the elements in `[nth, last)` is less than any of the elements in `[first, nth)`. In that sense, `nth_element` is more similar to `partition` than to `sort`. `Nth_element` does less work than `partial_sort`, so, reasonably enough, it is faster. That's the main reason to use `nth_element` instead of `partial_sort`.

[2] Note that this is significantly less than the run-time complexity of `partial_sort`.

### See also

`partial_sort`, `partition`, `sort`, StrictWeakOrdering, LessThan Comparable

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation