🪐 Алгоритмы диапазонов: Алгоритмы сортировки

Продолжаем серию о диапазонах — на очереди сортировка 🙂

Напомню: 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{} по умолчанию.


📍Навигация: Вакансии • Задачи • Собесы • Канал в Max

Библиотека C/C++ разработчика

#константная_правильность