C++ Algorithm nth_element()

30 Aug 2024 | 5 min read

C++ Algorithm nth_element() function is used to sort the elements between the first and nth element in ascending order and element between nth and last are not sorted. However, no element in between nth and last is smaller than an element between first and nth element.

The elements are compared using operator < for the first version, and comp for the second version.

Syntax

Parameter

first: A random access iterator pointing to the first element in the range to be used.

last: A random access iterator pointing to the past last element in the range to be used.

comp: A user-defined binary predicate function that accepts two arguments and returns true if the two arguments are in order and false otherwise. It follows the strict weak ordering to order the elements.

nth: A random access iterator addressing the position in the range[first, last) that will contain the sorted element.

Return value

None

Complexity

On average, complexity is linear in the distance between first and last: compares elements and possible swaps them, until the elements are properly rearranged.

Data races

The object in the range [first, last) are altered.

Exceptions

This function throws an exception if any of element comparison, element swap, or an operation on iterator throws an exception.

Note: The invalid parameters cause an undefined behavior.

Example 1

Let's see the simple example to demonstrate the use of nth_element():

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:

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:

Output:

myvector contains: 5 2 3 1 4 6 7 8 9

Example 4

Let's see another simple example:

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 )

Next TopicC++ Algorithm

← prev next →