Краткий ответ

std::nth_element переставляет элементы так, что на указанной позиции оказывается элемент, который занимал бы её в полностью отсортированном диапазоне. Все элементы слева от этой позиции не больше него, а все элементы справа — не меньше. При этом обе части диапазона сами по себе не обязаны быть отсортированы.

Исторический контекст

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

Именно эту задачу решает std::nth_element: он реализует перестановку диапазона вокруг заданной позиции, сохраняя требуемое отношение элементов к выбранному элементу.

Постановка проблемы

Предположим, требуется выбрать 100 самых дешёвых товаров из миллиона. Полная сортировка всех товаров корректна, но она выполняет больше работы, чем требуется: порядок внутри первой сотни и среди остальных элементов не важен.

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

Подробное решение

Пусть nth указывает на позицию элемента. После выполнения алгоритма выполняются два условия:

каждый элемент до nth не больше элемента в nth;
каждый элемент после nth не меньше элемента в nth.

Сам элемент в nth такой же, какой находился бы там после полной сортировки по тому же критерию. Однако элементы слева могут находиться в произвольном порядке, как и элементы справа.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{9, 1, 7, 3, 5, 2};
    auto nth = values.begin() + 2;

    std::nth_element(values.begin(), nth, values.end());

    std::cout << *nth << '
';
    for (auto it = values.begin(); it != nth; ++it)
        std::cout << *it << ' ';
}

В данном случае в nth окажется третье по величине значение, то есть 3. Два элемента до него будут не больше 3, но их порядок не гарантируется. Аналогично, элементы после него будут не меньше 3, но не обязательно будут образовывать отсортированную последовательность.

По числу сравнений алгоритм обычно требует линейное время в среднем, что выгоднее полной сортировки с логарифмическим множителем. Конкретные гарантии зависят от стандартной версии C++ и реализации; полагаться следует прежде всего на контракт алгоритма, а не на внутренний способ разбиения.

Если нужен отсортированный диапазон до позиции, после std::nth_element соответствующую часть можно отдельно отсортировать. Это сохраняет преимущество, когда требуется упорядочить только небольшой фрагмент, но добавляет стоимость сортировки выбранной части.

Алгоритм переставляет элементы диапазона, поэтому итераторы, ссылки и указатели на элементы могут продолжить указывать на те же объекты, если сами элементы не перемещаются контейнером вследствие перераспределения памяти. Однако значения, находящиеся по конкретным позициям, меняются, поэтому нельзя связывать позицию с прежним элементом после перестановки.

Компаратор должен задавать корректное строгое слабое упорядочивание. Если он противоречив или зависит от изменяемого внешнего состояния, результат алгоритма не следует считать надёжным.

Ситуация из практики

Сервис собирает миллион измерений и должен быстро получить медиану для расчёта порога тревоги. Вариант с полной сортировкой прост и даёт полностью упорядоченный массив, но тратит время на порядок, который дальше не используется.

Вариант с ручным последовательным поиском медианы требует отдельной реализации и легко содержит ошибки. Вариант с std::nth_element непосредственно выражает требуемую операцию: после него медианный элемент находится на нужной позиции, а его соседи разделены относительно него.

Выбором становится std::nth_element, потому что нужен только один порядковый элемент. Если после этого требуется вывести все значения в порядке возрастания, преимущество частичного выбора исчезает: выбранную часть или весь диапазон придётся дополнительно сортировать.

Что кандидаты часто упускают

1. Можно ли после std::nth_element взять первые k элементов как k наименьших?

Да, если алгоритм применён с позицией begin() + k, то первые k элементов будут не больше остальных элементов диапазона. Но они не будут отсортированы между собой. Если дальнейшая логика требует именно упорядоченный список, первые k элементов нужно дополнительно отсортировать.

2. Совпадает ли элемент в позиции nth с элементом, который был бы там после стабильной сортировки?

По значению и критерию порядка — да, позиция соответствует результату сортировки. Но при наличии эквивалентных элементов порядок таких элементов не сохраняется. std::nth_element не является стабильным алгоритмом, поэтому нельзя использовать его для сохранения исходного порядка равных объектов.

3. Чем std::nth_element отличается от std::partial_sort для поиска первых k элементов?

std::nth_element делит диапазон около границы и не сортирует выбранную часть. Он подходит, когда важен сам набор элементов или элемент на границе. std::partial_sort дополнительно сортирует первые k элементов, поэтому удобнее для получения уже упорядоченного топа, но обычно требует больше работы.