Recover Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttp://yahoo.com/
advanced search

Valid RSS

Computing › Stl › Algorithms › Sorting ›

nth_element

Sorts according to the nth position
+ View version details
Contents
  1. Definition
  2. Interface
  3. Description
  4. Return Value
  5. Complexity
  6. Page Comments

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.

Return Value

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

See Also

Last Modified: 2012-02-10 11:31:10     Page Rendered: 2012-05-23 08:12:03
 

Page Comments

 
 Format Excel Equations

  You must login to leave a messge