nth_element


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

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

Sort element in range

Rearranges the elements in the range [first,last), in such a way that the element at the resulting nth position is the element that would be in that position in a sorted sequence, with all the elements preceding it being smaller and all the elements following it greater than it. Neither the elements preceding it nor the elements following it are granted to be ordered.

The elements are compared using operator< for the first version, and comp for the second.

Parameters

first, last
Random-Access iterators to the initial and final positions of the sequence to be used. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
Notice that in this function, these are not consecutive parameters, but the first and third ones.
nth
Random-Access iterator pointing to the location within the range [first,last) that will have the sorted element.
comp
Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.


Return value

none

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
// nth_element example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool myfunction (int i,int j) { return (i<j); }

int main () {
  vector<int> myvector;
  vector<int>::iterator it;

  // set some values:
  for (int i=1; i<10; i++) myvector.push_back(i);   // 1 2 3 4 5 6 7 8 9

  random_shuffle (myvector.begin(), myvector.end());

  // using default comparison (operator <):
  nth_element (myvector.begin(), myvector.begin()+5, myvector.end());

  // using function as comp
  nth_element (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);

  // print out content:
  cout << "myvector contains:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}


Possible output:
myvector contains: 3 1 4 2 5 6 9 7 8


Complexity

On average, linear in the number of elements in [first,last).

See also

sort Sort elements in range (function template)
partial_sort Partially Sort elements in range (function template)
partition Partition range in two (function template)
find_if Find element in range (function template)