Declaration
template <class RandomAccessIterator> inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
Description The nth_element function is used to place in the location nth the element that would be there if the entire range [ first, last) \ were to be sorted. Also, for any iterator i in the range [ first, nth) and any iterator j in the range [ nth, last) , the element at location i is earlier in the sorted range than the element at location j, or the elements may compare as equal. For the first function comparisons are done using operator<, while for the second function they are done using the function object comp.
Type requirements
Group Sorting and related operations
Time complexity Linear on average.
Space complexity Constant.
Mutative? Yes.
Example Select here to view the source code for the example.
Implementation Select here to view source code (Copyright (C) 1994, Hewlett-Packard Company) for this algorithm.