Сортировки в C++

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

sort

sort(a.begin(), a.end());

Работает с вектором чего угодно, лишь бы для элементов был определён оператор <. Внутри — не чистая быстрая сортировка, а интроспективная: смесь быстрой, пирамидальной и вставок.

Логика такая. Основной ход — быстрая сортировка. Если глубина рекурсии стала подозрительно большой (значит, разделения идут плохо), библиотека переключается на пирамидальную, у которой $O(n \log n)$ гарантированы. А на коротких отрезках — десяток элементов — она переходит на вставки, потому что при таких размерах квадратичный алгоритм с маленькой константой просто быстрее.

Это общее место: у оптимального алгоритма обычно есть размер, ниже которого он проигрывает наивному.

Диапазоны и полуинтервалы

Все стандартные функции принимают полуинтервал: левая граница включается, правая нет. a.end() указывает не на последний элемент, а на место за ним.

Отсюда несколько следствий:

sort(a.begin(), a.end());              // весь вектор
sort(a.begin() + 2, a.begin() + 7);    // элементы с 2-го по 6-й
sort(a.rbegin(), a.rend());            // по убыванию
sort(a, a + n);                        // обычный массив, не вектор

Последняя строка работает потому, что имя массива в C++ — это указатель на его начало, а a + n указывает за конец. Никаких begin у такого массива нет и не нужно.

Сортировка по убыванию через rbegin/rend — это те же итераторы, только идущие в обратную сторону. Отдельный компаратор ради разворота писать незачем.

Компараторы

Когда порядок нужен не «по возрастанию значения», передают третьим аргументом функцию сравнения. Удобнее всего лямбдой:

int mod = 1000000000;
sort(a.begin(), a.end(), [&](int x, int y) {
    return x % mod < y % mod;
});

Квадратные скобки — список захвата. [&] означает «видеть все переменные из окружающего кода по ссылке»: именно так лямбда добирается до mod. Дальше в круглых скобках идут два сравниваемых элемента, а в теле — само сравнение.

Строгое сравнение обязательно

Компаратор обязан отвечать на вопрос «первый строго меньше второго». Для равных элементов он должен вернуть false.

Напрашивающееся <= вместо < — ошибка, и ошибка опасная: программа не выдаёт неверный ответ, а падает. Библиотека опирается на то, что из true следует «элементы точно различны», и при нарушении этого может выйти за границы массива.

sort(a.begin(), a.end(), [](int x, int y) { return x <= y; });  // так нельзя

Ошибка проявляется не сразу и не на маленьких тестах — тем она и коварна.

stable_sort

stable_sort(a.begin(), a.end());

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

Нужна она ровно тогда, когда сортируется что-то составное и порядок внутри равных значим.

nth_element

nth_element(a.begin(), a.begin() + k, a.end());

Ставит на позицию k тот элемент, который стоял бы там после сортировки, и раскидывает остальные: слева не большие, справа не меньшие. Внутри половин порядка нет.

Работает в среднем за линию — разбор в статье про порядковые статистики.

Мелочи, на которых теряют время

Передавайте контейнер по ссылке. Функция, объявленная как void solve(vector<int> a), получит копию: она отсортирует её и выбросит, а вызывающий код ничего не заметит. Нужно vector<int>& a. В рекурсивных функциях вроде quick_sort копия ещё и создаётся заново на каждом уровне.

i++ и ++i для чисел одинаковы. Разница появляется у итераторов: постфиксная форма обязана вернуть копию прежнего значения, и для сложных итераторов это заметно. Привычка писать ++it ничего не стоит и иногда экономит.

Документация под рукой. У стандартной библиотеки много деталей, и держать их в голове не нужно. На cppreference.com есть описание каждой функции с примерами; на олимпиадах этот сайт обычно доступен.

Если вы пишете на Python

Там всё устроено иначе: порядок задаётся ключом, а не компаратором, устойчивость гарантирована стандартом, а аналога nth_element нет вовсе. Разбор — в следующей статье раздела.