Standard C++ Library Class Reference

Description
The nth_element algorithm rearranges a collection according to either the default comparison
operator (>) or the provided comparison operator. After the algorithm applies, three things are
true:
The element that would be in the nth position if the collection were completely sorted is
in the nth position
●
All elements prior to the nth position would precede that position in an ordered collection●
All elements following the nth position would follow that position in an ordered
collection
●
That is, for any iterator i in the range [first, nth) and any iterator j in the range [nth, last) it holds
that !(*i > *j) or comp(*i, *j) == false.
Note that the elements that precede or follow the nth postion are not necessarily sorted relative
to each other. The nth_element algorithm does not sort the entire collection.
Complexity
The algorithm is linear, on average, where N is the size of the range [first, last).
Example
//
// nthelem.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
template<class RandomAccessIterator>
void quik_sort(RandomAccessIterator start,
RandomAccessIterator end)
{
size_t dist = 0;
distance(start, end, dist);
//Stop condition for recursion
if(dist > 2)
{
//Use nth_element to do all the work for quik_sort
nth_element(start, start+(dist/2), end);
//Recursive calls to each remaining unsorted portion
quik_sort(start, start+(dist/2-1));
quik_sort(start+(dist/2+1), end);
}