Чем интересен вариант использования алгоритма C ++ nth_element?

Question

Я нашел много вопросов и ответов о том, как использовать алгоритм nth_element в C ++ STL, но до сих пор я не нашел ни одного интересного варианта его использования. В частности, в каком реальном случае использования я бы использовал nth_element вместо простой сортировки всего вектора?

РЕДАКТИРОВАТЬ: Очевидно, nth_element может использоваться, чтобы найти медиану или другой процентиль данных, но это кажется неэффективным, поскольку это изменяет вектор.

Answer 1

Типичным случаем использования является случай, когда нужно избежать сортировки всего набора, потому что он большой. Если вам просто нужен верхний n, то для разделения набора используется nth_element. Первый раздел содержит верхние n элементов.

Answer 2

Вы хотите ответить "что такое медиана?" набора данных. Не нужно сортировать, вам нужна запись, где 50% больше, а 50% меньше.