CodeCogs

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 first 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

http://www.tenouk.com/

Example 1

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

http://www.smu.ca/academic/science/compsci/

Example 2

Problem

This program illustrates the use of the STL nth_element() algorithm (extended 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. In this case the order of the elements is determined by one integer preceding another if and only if it has a smaller digit sum.

Workings

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/* Tests if one integer has a smaller digit sum than another.
   i1 and i2 have been initialized and i1, i2 are both > 0.
   Returns true if sum of the digits in i1 is < sum of digits in i2, and otherwise returns false. */

bool hasSmallerDigitSum(int i1, int i2)
{
  int digitSum1 = 0;
  while (i1 != 0)
  {
    digitSum1 += i1 % 10;
    i1 /= 10;
  }

  int digitSum2 = 0;
  while (i2 != 0)
  {
    digitSum2 += i2 % 10;
    i2 /= 10;
  }
  return digitSum1 < digitSum2;
}

int main()
{
  int a[] = {92,  21,  53, 84,  46,  13, 41, 76,  45,  61,  11,  15};
  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(), hasSmallerDigitSum);

  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:
92 21 53 84 46 13 41 76 45 61 11 15

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:
11 21 13 41 15 61 53 45 46 92 84 76

References

http://www.smu.ca/academic/science/compsci/

nth_element

Definition

Interface

Description

Return Value

Complexity

References

Example 1

Example 2

See Also