Сортировка — это просто ещё один алгоритм
На предыдущей странице вы увидели, что стандартная библиотека поставляет готовые алгоритмы, работающие с любым диапазоном через итераторы. Сортировка — тот алгоритм, к которому вы будете обращаться чаще всего, и у неё своя страница, потому что у неё есть несколько острых углов: пользовательские порядки, стабильность и правило, нарушив которое, вы получаете неопределённое поведение вместо неправильного ответа.
Рабочая лошадка — std::sort из <algorithm>. Вы передаёте ему начало и конец диапазона, и он переупорядочивает элементы на месте по возрастанию:
Копия не создаётся — переупорядочивается сам вектор. Под капотом std::sort обычно представляет собой introsort (быстрая сортировка с откатом к пирамидальной), что даёт в среднем O(n log n). Это почти всегда быстрее и куда менее подвержено ошибкам, чем писать собственную сортировку.
Он работает и с обычными C-массивами — просто опишите диапазон указателями:
Пользовательский порядок с компаратором
По умолчанию std::sort упорядочивает элементы через operator<. Чтобы сортировать иначе, передайте третий аргумент — компаратор, который принимает два элемента и возвращает true, если первый должен идти перед вторым.
Лямбда подходит естественно. Порядок по убыванию — это просто a > b:
Для распространённого случая простого убывающего порядка для встроенных типов библиотека даже поставляет готовый компаратор greater<T>() из <functional>:
#include <functional>
sort(nums.begin(), nums.end(), greater<int>()); // то же, что и a > b
Компаратор — это также способ сортировать по чему-то отличному от самого значения; например, сортировать строки по длине, а не по алфавиту:
Принимайте параметры компаратора по const& для всего, что больше пары байт (как string): копировать каждый элемент при каждом сравнении — чистая трата ресурсов.
Сортировка структур по полю
В реальных программах вы обычно сортируете коллекции структур по одному из их полей. Компаратор просто обращается к нужному полю. Здесь мы сортируем людей по возрасту, от самых молодых:
Обратите внимание, что Linus и Dennis оба в возрасте 25 лет. Здесь они вышли в исходном относительном порядке, но std::sort этого не гарантирует. Если относительный порядок равных элементов важен, используйте std::stable_sort, который его сохраняет (за небольшую плату в производительности):
Чтобы намеренно разрешать ничьи — скажем, сортировать по возрасту, а затем по алфавиту по имени — сравнивайте вторичный ключ только когда первичные ключи равны. std::tie делает это аккуратно:
Ловушка строгого слабого порядка
Это самая опасная ошибка при сортировке в C++, потому что она не даёт неправильный ответ — она даёт неопределённое поведение, что часто означает сбой или чтение за границами.
std::sort требует, чтобы ваш компаратор задавал строгий слабый порядок. Практическое правило: comp(x, x) должно быть false для любого элемента x. Иными словами, элемент никогда не идёт «перед» самим собой. Именно это дают < и > и именно это нарушают <= и >=:
// БАГ: возвращает true, когда a == b, нарушая строгий слабый порядок.
sort(v.begin(), v.end(), [](int a, int b) {
return a <= b; // неопределённое поведение — может упасть на некоторых входах
});
С <= компаратор утверждает, что 5 идёт перед другой 5, что противоречиво. Тогда std::sort может увести указатель за конец диапазона. Маленькие входные данные иногда кажутся работающими, что делает этот баг пугающим: он может пройти ваши тесты и упасть в продакшене. Исправление — просто <:
Вторая классическая ловушка: сортировка делает недействительным всё, что указывает внутрь диапазона. Итераторы, указатели и индексы, сохранённые до сортировки, после неё уже не ссылаются на тот же логический элемент, потому что элементы сдвинулись. Заново вычисляйте любую нужную позицию после сортировки, никогда — до.
Сортировка части диапазона
Иногда вам не нужно сортировать всё — вам нужны лишь несколько первых. Сортировать весь вектор, чтобы прочитать первые три, расточительно. std::partial_sort упорядочивает только запрошенные элементы, а остальные оставляет в неопределённом порядке, что дешевле:
А если вам нужен лишь один элемент, который оказался бы на заданной позиции — например, медиана — std::nth_element делает ещё меньше работы: он помещает нужный элемент на этот индекс, со всеми меньшими перед ним и всеми большими после, всё в среднем за O(n).
Обращайтесь к ним, когда «полностью отсортировано» — это больше, чем на самом деле требует задача: на больших данных они экономят реальное время.
Далее: Шаблоны
Заметили ли вы, что один и тот же std::sort справился с int, string и вашей собственной структурой Person, а greater<int>() с тем же успехом мог бы быть greater<string>()? Эта универсальность — не магия, это шаблоны (templates), механизм, позволяющий одному фрагменту кода работать с любым типом, который подставит вызывающая сторона. На следующей странице мы увидим, как писать собственные шаблонные функции и классы, чтобы ваш код мог быть таким же независимым от типа, как алгоритмы, которыми вы пользовались.
Часто задаваемые вопросы
Как отсортировать вектор в C++?
Подключите <algorithm> и вызовите sort(v.begin(), v.end()). Это сортирует элементы на месте по возрастанию с помощью operator<. Чтобы отсортировать массив, передайте arr и arr + n (или begin(arr) / end(arr)).
Как отсортировать по убыванию в C++?
Передайте компаратор, возвращающий a > b: sort(v.begin(), v.end(), [](int a, int b){ return a > b; });. Можно также использовать встроенный sort(v.begin(), v.end(), greater<int>()); из <functional>.
Почему мой компаратор вызывает сбой std::sort в C++?
Ваш компаратор должен задавать строгий слабый порядок (strict weak ordering): он обязан возвращать false, когда оба аргумента равны. Использование <= или >= (которые возвращают true для равных элементов) нарушает это правило и является неопределённым поведением — std::sort может выйти за границы и упасть. Всегда сравнивайте через < или >.
