nth_element() in C++

Syntax of nth_element()

The syntax for the nth element() method in C++ is:

Here, *begin is the pointer to the first element of the list, which will be rearranged, *nth is the pointer to the position in the list, which will point to the nth element, and *end is the pointer to the last element of the list. The last parameter is optional and is a boolean user-defined custom function that can be used for customizing elements.

Let us look at a detailed description of each of these parameters.

Parameter of nth_element()

The nth_element method (or n-element function) in C++ STL takes three and one optional parameters. These parameters are:

• *begin: This pointer points to the first element of the list, which will be rearranged to get the nth element.
• *nth: This pointer points to the index of the nth element in the list. After the method is operated, the resultant element will be at this index in the list.
• *end: This pointer points to the last element of the list, which will be rearranged to get the nth element.
• comp: This is an optional parameter. It is a boolean user-defined method that, if provided, is used to compare and rearrange the list elements. Hence, this method takes two elements as parameters, and if it returns true, those elements are considered to be in the correct order, or their order is swapped.

Return Values Of nth_element()

The function rearranges the elements in the list to which the iterators belong so that the element which would be at the nth position in the sorted order is brought to its correct place. Hence, it just rearranges the elements in the range pointed to by the iterators *begin and *end and does not care about the orders. This is why the function does not return anything and is a void function.

Exceptions Of nth_element()

There are some exceptions in the function nth_element() (or n element) such as:

• nth_element() (or n element function) will throw an exception if any of the element comparisons, that is, the element swaps or the operation or the moves on the elements or iterators, throws an exception.

Example of nth_element()

Let us look at an example of how to use this method in C++.

Output

In the above example, after the nth_element() method in C++ is applied, the element at the fourth position is the one that would have been at that place if the array had been sorted. Also, even though the vector isn't sorted, the elements before the fourth position are less than it, and the elements after the fourth position are greater than that element after the operation has been applied.

Complexity

The complexity of the nth_element() function in C++ STL is O(m), where m is the number of elements in the range pointed to by the *begin and *end iterators. Hence, it functions in linear time complexity as it just rearranges the elements in the list.

As for the space complexity, it works in O(m) space, where again, m is the number of elements in the range pointed to by the *begin and *end iterators if we consider the space where the changes happen in the array, whereas it takes extra O(1) space if we do not consider the space occupied by the array.

What is nth_element()?

The nth_element() is a function in C++ STL that rearranges the elements of a list so that the element at the nth position or the nth element in that sorted list is brought to its correct place. Let us look at an example.

Consider an array [3, 9, -1, 0, 12, 6, -4]. Suppose we apply the nth_element method on this array, with n being 4. This means that after the operation, we want the element which would be in the 4th position in the sorted list to be brought to its correct place. Hence, after we apply the nth element method with n = 4, the array will be [0, -4, -1, 3, 6, 9, 12]. As you can see, the array was not completely sorted, but the elements before the nth element(the fourth element, which is at index 3) are at their correct place, as the other elements may or may not be at their correct place.

More Examples

• Comparing elements using “< "

Let us explore the standard version of nth_element() (or n-element function), where the comparison is based on the values of the elements present in the array. This version would find the nth element if the array were sorted in ascending order.

Syntax

Let us take a look at an example to understand this better.

Example

Output

In the above code, we wanted to know if the 4th element, 34 if the array, was sorted in ascending order. All the elements to the left of 34 are smaller than 34, whereas all the elements to its right are greater than it. However, the elements jumbled on both sides and needed to be sorted.

This is not the only way we can use nth_element() (or n element function). We can also find the nth element based on a custom sort that we pass on to the function. Let us take a look at such an example.

• Comparing using a pre-defined function

In nth_element() (or n-element function), we can also pass a custom function of our choice which will help in finding the nth_element() based on the logic that we provide.

Syntax

Let us take a look at a few examples to understand this better.

Example

Find the nth element if the array is sorted in descending order

Output

In the above code, we wanted to know if the 6th element, 13 of the array, was sorted in descending order.

But this time, If you notice, you can see that all the elements to the left of 13 are greater than 13, whereas all the elements to its right are smaller than it and jumbled on both sides. This happens due to our custom sort/comparison function that we have passed in the nth_element() function.

Let us take a look at another example to understand this even further.

Example

Find the nth element if the array is sorted with all the even numbers sorted in ascending order first and then all the odd numbers sorted in ascending order.

Output

In the above code, we wanted to know if the 6th element, which is 13 if the array was sorted with all the even numbers sorted in ascending order first and then all the odd numbers sorted in ascending order.

If you notice, you can see that all the elements to the left of 13 are either smaller odd numbers or all the even numbers, whereas all the elements to its right are greater than it and jumbled on both sides. Again, this happens due to our custom sort/comparison function that we passed in the nth_element() function, which wanted to sort based on the logic we had provided.

See Also

• max_element()
• min_element()
• partial_sort_copy()
• stable_sort()
• sort()