c++algorithmc++11stlnth-element

Finding nth largest element inplace

I need to find nth largest element in an array and currently I'm doing it the following way:

std::vector<double> buffer(sequence); // sequence is const std::vector<double>
std::nth_element(buffer.begin(), buffer.begin() + idx, buffer.end(), std::greater<double>());
nth_element = buffer[idx];

But is there any way to find the n-th largest element in an array without using an external buffer?

Solution

  • You can avoid copying the entire buffer without modifying the original range by using std::partial_sort_copy. Simply copy the partially sorted range into a smaller buffer of size n, and take the last element.

    If you may modify the original buffer, then you can simply use std::nth_element in place.