nth_element

Partition a range by its nth element.

If the value referenced by n is value , partition the sequence [ first...last ) so that all elements to the left of value are less than or equal to value , and all elements to the right of value are greater than or equal to value . The first version uses operator< to perform the comparisons, whereas the second version uses the binary function compare .

Library

Standards<ToolKit>

Declaration


#include <algorithm>

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

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

Complexity

Time complexity is O(N), where N is ( last - first ). Space complexity is constant.

Example <ospace/osstd/examples/nthelem0.cpp>
#include <iostream>
#include <algorithm>

int numbers[ 6 ] = { 5, 2, 4, 1, 0, 3 };

void
main()
  {
  nth_element( numbers, numbers + 3, numbers + 6 );

  for ( int i = 0; i < 6; ++i )
    cout << numbers[ i ] << ` `;
  cout << "\n";
  }

1 0 2 3 4 5
Example <ospace/osstd/examples/nthelem1.cpp>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <iterator>
#include <vector>

void
main()
  {
  vector< int > v1( 10 );
  for ( int i = 0; i < v1.size(); ++i )
    v1[ i ] = rand() % 10;
  ostream_iterator< int > iter( cout, " " );
  copy( v1.begin(), v1.end(), iter );
  cout << "\n";

  nth_element( v1.begin(), v1.begin() + v1.size() / 2, v1.end() );

  copy( v1.begin(), v1.end(), iter );
  cout << "\n";
  }

6 0 2 0 6 7 5 5 8 6
5 0 2 0 5 6 7 6 8 6
Example <ospace/osstd/examples/nthelem2.cpp>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <functional>
#include <iterator>
#include <vector>

void
main()
  {
  vector< int > v1( 10 );
  for ( int i = 0; i < v1.size(); ++i )
    v1[ i ] = rand() % 10;
  ostream_iterator< int > iter( cout, " " );
  copy( v1.begin(), v1.end(), iter );
  cout << "\n";

  nth_element
    (
    v1.begin(),
    v1.begin() + v1.size() / 2,
    v1.end(),
    greater< int >()
    );

  copy( v1.begin(), v1.end(), iter );
  cout << "\n";
  }

6 0 2 0 6 7 5 5 8 6
6 8 7 6 6 5 5 2 0 0

Copyright©1994-2026 Recursion Software LLC
All Rights Reserved - For use by licensed users only.