The C++ algorithm nth_element function is employed to arrange the elements from the initial element up to the nth element in an ascending order, while the elements between the nth and last positions are left unsorted. It ensures that no element between the nth and last positions is smaller than any element between the first and nth positions.
The elements are compared using the operator < in the initial version, and comp in the subsequent iteration.
Syntax
default (1) template <class RandomAccessIterator>
void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
custom (2) template <class RandomAccessIterator, class Compare>
void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);
Parameter
A random access iterator pointing to the initial element within the specified range for operation.
last: An iterator with random access capability pointing to the element before the last one in the specified range.
comp : A custom binary predicate function that takes two parameters and outputs true if they are in sequence, else false. It adheres to the strict weak ordering for element arrangement.
nth: An iterator that allows for random access and points to the position within the range [first, last) where the element to be sorted will be placed.
Return value
Complexity
On average, the complexity increases linearly with the distance between the first and last elements. It involves comparing elements and potentially swapping them until the elements are correctly reorganized.
Data races
The items within the range [first, last) are modified.
Exceptions
This function will raise an exception if an error occurs during element comparison, element swapping, or any iterator operation.
Note: The invalid parameters cause an undefined behavior.
Example 1
Let's examine a basic example to showcase the functionality of nth_element:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(vector<int> ar)
{
for(auto x : ar) cout << x << " ";
cout << endl;
}
int main()
{
vector<int> ar = {1, 3, 6, 1, 2, 4, 7, 0};
cout<<"Before: ";
// will print 1 3 6 1 2 4 7 0
print(ar);
// mid = 5th element (ar.begin() + 4)
auto mid = ar.begin() + distance(ar.begin(), ar.end()) / 2;
// lets nth_element ar to mid
nth_element(ar.begin(), mid, ar.end());
cout<<"\nAfter: ";
// will print 2 0 1 1 3 4 7 6
// mid points to element 3
print(ar);
return 0;
}
Output:
Before: 1 3 6 1 2 4 7 0
After: 2 0 1 1 3 4 7 6
Example 2
Let's see another simple example:
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int main()
{
vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};
cout<<"Elements are: ";
for (vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
cout << ' ' << *it;
cout << '\n';
nth_element(v.begin(), v.begin() + v.size()/2, v.end());
cout << "The median is " << v[v.size()/2] << '\n';
nth_element(v.begin(), v.begin()+1, v.end(), greater<int>());
cout << "The second largest element is " << v[1] << '\n';
return 0;
}
Output:
Elements are: 5 6 4 3 2 6 7 9 3
The median is 5
The second largest element is 7
Example 3
Let's see another simple example:
#include <iostream> // std::cout
#include <algorithm> // std::nth_element, std::random_shuffle
#include <vector> // std::vector
using namespace std;
bool myfunction (int i,int j) { return (i<j); }
int main () {
vector<int> myvector;
// 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 (vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
cout << ' ' << *it;
cout << '\n';
return 0;
}
Output:
myvector contains: 5 2 3 1 4 6 7 8 9
Example 4
Let's see another simple example:
#include <vector>
#include <algorithm>
#include <functional> // For greater<int>( )
#include <iostream>
// Return whether first element is greater than the second
bool UDgreater ( int elem1, int elem2 ) {
return elem1 > elem2;
}
int main() {
using namespace std;
vector <int> v1;
vector <int>::iterator Iter1;
int i;
for ( i = 0 ; i <= 5 ; i++ )
v1.push_back( 3 * i );
int ii;
for ( ii = 0 ; ii <= 5 ; ii++ )
v1.push_back( 3 * ii + 1 );
int iii;
for ( iii = 0 ; iii <= 5 ; iii++ )
v1.push_back( 3 * iii +2 );
cout << "Original vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
nth_element(v1.begin( ), v1.begin( ) + 3, v1.end( ) );
cout << "Position 3 partitioned vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
// To sort in descending order, specify binary predicate
nth_element( v1.begin( ), v1.begin( ) + 4, v1.end( ),
greater<int>( ) );
cout << "Position 4 partitioned (greater) vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
random_shuffle( v1.begin( ), v1.end( ) );
cout << "Shuffled vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
// A user-defined (UD) binary predicate can also be used
nth_element( v1.begin( ), v1.begin( ) + 5, v1.end( ), UDgreater );
cout << "Position 5 partitioned (UDgreater) vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
return 0;
}
Output:
Original vector:
v1 = ( 0 3 6 9 12 15 1 4 7 10 13 16 2 5 8 11 14 17 )
Position 3 partitioned vector:
v1 = ( 1 0 2 3 8 5 9 4 7 6 10 16 13 15 12 11 14 17 )
Position 4 partitioned (greater) vector:
v1 = ( 16 17 14 15 13 12 11 9 7 8 10 6 1 4 5 3 2 0 )
Shuffled vector:
v1 = ( 13 10 6 3 5 2 0 17 11 8 15 9 7 14 16 1 12 4 )
Position 5 partitioned (UDgreater) vector:
v1 = ( 14 17 15 16 13 12 10 11 9 8 0 2 7 5 3 1 6 4 )
