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

В реальных соревнованиях почти никогда не стоит писать собственную реализацию сортировки. В стандартной библиотеке C++ уже есть эффективная и хорошо протестированная функция sort, которая работает за O(n log n) и в большинстве случаев является оптимальным выбором.

Использование стандартной функции даёт сразу несколько преимуществ:

• экономия времени на написание кода;
• надёжность (реализация протестирована);
• высокая производительность;
• гибкость (можно задавать свой способ сравнения).

---

Сортировка вектора

Самый распространённый случай — сортировка vector.

vector<int> v = {7, 2, 9, 1, 5, 2};
sort(v.begin(), v.end());

После сортировки:

[1, 2, 2, 5, 7, 9]

По умолчанию элементы сортируются по возрастанию.

Сортировка по убыванию

Чтобы отсортировать по убыванию, можно использовать обратные итераторы:

sort(v.rbegin(), v.rend());

Теперь результат будет:

[9, 7, 5, 2, 2, 1]

---

Сортировка обычного массива

Если используется статический массив:

int a[] = {7, 2, 9, 1, 5, 2};
int n = 6;

sort(a, a + n);

Принцип тот же: передаём указатель на начало и указатель на конец диапазона.

---

Сортировка строки

Строка в C++ — это по сути динамический массив символов, поэтому её тоже можно сортировать:

string s = "zebra";
sort(s.begin(), s.end());

Результат:

"aberz"

Символы сортируются по их ASCII-коду (фактически — в алфавитном порядке).

---

Сортировка пар (pair)

Тип pair уже имеет встроенный оператор сравнения.

Сортировка происходит:

1. Сначала по first
2. При равенстве — по second

Пример:

vector<pair<int,int>> v;

v.push_back({2, 5});
v.push_back({1, 7});
v.push_back({2, 1});

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

После сортировки:

(1,7)
(2,1)
(2,5)

---

Сортировка кортежей (tuple)

tuple сравнивается лексикографически:

• сначала по первому элементу,
• затем по второму,
• затем по третьему и т.д.

vector<tuple<int,int,int>> v;

v.push_back({3,1,4});
v.push_back({2,9,1});
v.push_back({3,1,2});

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

Результат:

(2,9,1)
(3,1,2)
(3,1,4)

---

Пользовательские структуры

Для своих структур нужно определить оператор <.

Пример: сортировка точек сначала по x, затем по y.

struct Point {
    int x, y;

    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

Теперь можно писать:

vector<Point> v;
sort(v.begin(), v.end());

---

Своя функция сравнения

Иногда удобно задать отдельную функцию сравнения.

Например, отсортируем строки:

• сначала по длине,
• при равной длине — по алфавиту.

bool comp(string a, string b) {
    if (a.size() != b.size()) 
        return a.size() < b.size();
    return a < b;
}

sort(v.begin(), v.end(), comp);

---

Важные замечания

1. Сложность

sort работает за O(n log n).

2. Стабильность

Обычный sort не является стабильной сортировкой. Если важен порядок равных элементов — используйте stable_sort:

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

3. Частичная сортировка

Иногда нужно отсортировать только часть массива:

sort(v.begin(), v.begin() + k);

Или найти k-й по величине элемент:

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

После этого:

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

---

Когда сортировка особенно полезна

Сортировка часто используется как подготовительный шаг:

• поиск одинаковых элементов;
• поиск медианы;
• двухуказательные методы;
• жадные алгоритмы;
• бинарный поиск по отсортированному массиву.

Во многих задачах грамотное применение sort позволяет резко упростить решение.

---

Итог

В соревнованиях:

• почти всегда используйте std::sort;
• не пишите собственные пузырьковые или другие O(n²) сортировки;
• активно применяйте пользовательские компараторы;
• помните о stable_sort и nth_element.