Place element in location where it would be sorted

Source code

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

• RandomAccessIterator must be a regular random access iterator .
• Compare must be a function object type that provides int operator()(S, S), where S is the dereference type of RandomAccessIterator.

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.