Sorts according to the nth position
You're viewing an older version of this page (#4165). View the current version.
View versions (1)
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
Example 1
ProblemThis 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;
}
SolutionOutput:
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
Example 2
ProblemThis 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;
}
SolutionOutput:
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
See Also
