Finding nth largest element inplace

Question

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?

Answer 1

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.

Answer 2

You can use the partition function used in Quick Sort to find the nth largest elements.

The partition function will divide the original array into two parts.The first part will be smaller than A[i], The second part will be larger than A[i],partition will return i.If i is equal to n, then return A[i].If i is smaller than n,then partition the second part.If i is larger than n,then partition the first part.

It won't cost you extra buffer,and the average time cost is O(n).