🪐 Алгоритмы диапазонов: Алгоритмы сортировки — 29 мая 2026 г. в 07:44:15.336
🪐 Алгоритмы диапазонов: Алгоритмы сортировки Продолжаем серию о диапазонах — на очереди сортировка 🙂 Напомню: std::ranges::* принимают диапазоны целиком и поддерживают проекции. Если пропустили предыдущий пост про алгоритмы поиска — начните с него. 🧋 ranges::sort — классическая сортировка std::vector<int> v = {5, 3, 1, 4, 2}; std::ranges::sort(v); // {1, 2, 3, 4, 5} std::ranges::sort(v, std::greater{}); // {5, 4, 3, 2, 1} Один аргумент вместо пары итераторов. Второй аргумент — компаратор: std::greater{} для сортировки по убыванию, {} (или ничего) — по возрастанию. ❗️ ranges::sort требует random access range — std::vector, std::array, std::deque подойдут, а std::list — нет (для него есть метод list::sort()). 🍿 ranges::stable_sort — сохраняем порядок равных struct Task { std::string name; int priority; }; std::vector<Task> tasks = { {"Почта", 2}, {"Код", 1}, {"Тесты", 2}, {"Деплой", 1} }; std::ranges::stable_sort(tasks, {}, &Task::priority); // {{"Код", 1}, {"Деплой", 1}, {"Почта", 2}, {"Тесты", 2}} // Элементы с одинаковым priority сохранили исходный порядок Если два элемента «равны» по компаратору, stable_sort гарантирует, что их взаимный порядок останется таким же, как в исходном диапазоне. Обычный sort такой гарантии не даёт. 🍨 ranges::partial_sort — сортируем только первые N std::vector<int> v = {5, 3, 1, 4, 2}; std::ranges::partial_sort(v, v.begin() + 3); // {1, 2, 3, ?, ?} — первые три отсортированы, остальные в произвольном порядке Полезно, когда нужен «топ-N» без затрат на полную сортировку. Сложность O(N·log(K)) вместо O(N·log(N)), где K — количество нужных элементов. 🍋 ranges::partial_sort_copy — топ-N в отдельный буфер std::vector<int> v = {5, 3, 1, 4, 2}; std::vector<int> top3(3); // буфер под результат std::ranges::partial_sort_copy(v, top3); // top3 == {1, 2, 3} // v не изменился: {5, 3, 1, 4, 2} Работает как partial_sort, но не трогает исходный диапазон — результат пишется в отдельный контейнер. Размер приёмника определяет K (сколько элементов попадёт в «топ»). Удобно, когда исходные данные нельзя модифицировать. // Топ-2 самых старших — без изменения исходного вектора std::vector<Person> oldest(2); std::ranges::partial_sort_copy(people, oldest, std::greater{}, &Person::age); 👀 ranges::nth_element — найти N-й по порядку std::vector<int> v = {5, 3, 1, 4, 2}; std::ranges::nth_element(v, v.begin() + 2); // v[2] == 3 (медиана) // Все элементы слева <= 3, справа >= 3, но внутри групп порядок произвольный Элемент на позиции N оказывается тем же, что стоял бы там после полной сортировки. Идеален для поиска медианы или перцентилей. Средняя сложность — O(N). 🐾 ranges::is_sorted — проверка отсортированности std::vector<int> a = {1, 2, 3, 4, 5}; std::vector<int> b = {1, 3, 2, 4, 5}; bool ok1 = std::ranges::is_sorted(a); // true bool ok2 = std::ranges::is_sorted(b); // false // Найти, где порядок нарушается auto it = std::ranges::is_sorted_until(b); // *it == 2 — первый элемент, нарушающий порядок is_sorted — быстрая проверка перед бинарным поиском или мержем. is_sorted_until возвращает итератор на первый элемент, который «ломает» порядок. 🍕 Проекции — работают и в сортировках struct Person { std::string name; int age; }; std::vector<Person> people = {{"Алиса", 30}, {"Борис", 25}, {"Вера", 35}}; // Сортировка по возрасту — без лямбды std::ranges::sort(people, {}, &Person::age); // {{"Борис", 25}, {"Алиса", 30}, {"Вера", 35}} // По убыванию возраста std::ranges::sort(people, std::greater{}, &Person::age); // Топ-2 самых старших std::ranges::partial_sort(people, people.begin() + 2, std::greater{}, &Person::age); is_sorted — быстрая проверка перед бинарным поиском или мержем. is_sorted_until возвращает итератор на первый элемент, который «ломает» порядок. ❗️ Проекция — третий аргумент (после компаратора). {} на месте компаратора означает std::less{} по умолчанию.