• http://facebook.com/
• https://www.google.com/accounts/o8/id
• https://me.yahoo.com

# nth_element

Sorts according to the nth position

## Definition

The nth_element() algorithm is defined in the standard header <algorithm> and in the nonstandard backward-compatibility header <algo.h>.

## Interface

```#include <algorithm>
template < class RandomAccessIterator >
void nth_element(
RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last
);
template < class RandomAccessIterator, class BinaryPredicate >
void nth_element(
RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last,
BinaryPredicate comp
);```

Parameters:
Parameter Description
first A random-access iterator addressing the position of the first element in the range to be partitioned
last A random-access iterator addressing the position one past the final element in the range to be partitioned
nth A random-access iterator addressing the position of element to be correctly ordered on the boundary of the partition
comp User-defined predicate function object that defines the comparison criterion to be satisfied by successive elements in the ordering. A binary predicate takes two arguments and returns `true` when satisfied and `false` when not satisfied

## Description

Nth_element function sorts the elements between the `fi rst` and the `nth` element in ascendant order. The elements between the `nth` element and the `last` are not sorted, however no element in between the `nth` and the `last` is smaller than an element between the `first` and the `nth` element.

The first version compares objects using `operator<` and the second compares objects using a function object `comp`.

None.

## Complexity

The complexity is linear; performs `last - first` on average.

### References

Example:
##### Example - nth_element function
Problem
This program illustrates the use of the STL nth_element() algorithm (default version) to partition a vector of integers of size 12 around its 7th element.

The ranges on either side of this value may or may not be sorted, but the algorithm does not guarantee this, and you should not expect it.
Workings
```#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
int a[] = {10,  2,  6, 11,  9,  3, 4, 12,  8,  7,  1,  5};
vector<int> v(a, a+12);
cout <<"\nHere are the initial contents of the vector:\n";
for (vector<int>::size_type i=0; i<v.size(); i++)
cout <<v.at(i)<<" ";

cout <<"\nNow we make the following call:";
cout <<"\nnth_element(v.begin(), v.begin()+6, v.end());";
nth_element(v.begin(), v.begin()+6, v.end());

cout <<"\nAnd here are the contents of the vector partitioned around its 7th element:\n";
for (vector<int>::size_type i=0; i<v.size(); i++)
cout<<v.at(i)<<" ";

return 0;
}```
Solution
Output:

Here are the initial contents of the vector:
10 2 6 11 9 3 4 12 8 7 1 5

Now we make the following call:
nth_element(v.begin(), v.begin()+6, v.end());

And here are the contents of the vector partitioned around its 7th element:
1 2 3 4 5 6 7 8 9 10 11 12
References