Перейти к содержанию

3.1 Теория сортировки

Сортировка — одна из фундаментальных задач алгоритмики. Во многих задачах данные гораздо проще анализировать, если они расположены в упорядоченном виде.

Например:

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

В этом разделе мы рассмотрим:

  • простые алгоритмы сортировки O(n²),
  • эффективные алгоритмы O(n log n),
  • нижнюю границу для сортировки,
  • линейную сортировку при специальных условиях.

Базовая задача

Задача: Дан массив из n элементов. Нужно отсортировать его по неубыванию.

Пример:

4 7 1 9 3 7 2

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

1 2 3 4 7 7 9

Алгоритмы O(n²)

Простейшие алгоритмы сортировки содержат два вложенных цикла. Их сложность — O(n²).

Сортировка пузырьком (Bubble Sort)

Идея: многократно проходить по массиву и менять соседние элементы местами, если они стоят в неправильном порядке.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n-1; j++) {
        if (a[j] > a[j+1]) {
            swap(a[j], a[j+1]);
        }
    }
}

После первого прохода самый большой элемент окажется в конце массива. После второго — второй по величине. И так далее.

Инверсии

Инверсия — это пара индексов (i, j), где:

  • i < j
  • a[i] > a[j]

То есть элементы стоят в неправильном порядке.

Пример:

2 5 3 4 1

Чем больше инверсий, тем дальше массив от отсортированного состояния.

В массиве, упорядоченном в обратном порядке, число инверсий равно:

n(n-1)/2 = O(n²)

Каждый обмен соседних элементов в пузырьковой сортировке устраняет ровно одну инверсию. Поэтому в худшем случае требуется O(n²) операций.

Алгоритмы O(n log n)

Чтобы сортировать быстрее, применяются алгоритмы "разделяй и властвуй".

Сортировка слиянием (Merge Sort)

Алгоритм:

  1. Разделить массив пополам.
  2. Рекурсивно отсортировать каждую половину.
  3. Слить две отсортированные части.

Пример:

4 7 1 9 3 7 2 6

После разделения и сортировки половин:

1 4 7 9 | 2 3 6 7

После слияния:

1 2 3 4 6 7 7 9

Почему O(n log n)?

  • Глубина рекурсии — log n.
  • На каждом уровне выполняется O(n) работы.

Итоговая сложность — O(n log n).

Нижняя граница сортировки

Если алгоритм основан только на сравнении элементов, то быстрее O(n log n) сортировать невозможно.

Причина: существует n! различных перестановок массива. Чтобы различить их, требуется минимум log₂(n!) сравнений.

Асимптотически:

log(n!) ≈ n log n

Следовательно, нижняя граница для сортировок на основе сравнений — Ω(n log n).

Линейная сортировка: Counting Sort

Если элементы — целые числа из диапазона 0…C, и C = O(n), можно отсортировать массив за O(n).

Идея

  1. Создать массив частот.
  2. Подсчитать, сколько раз встречается каждое число.
  3. Восстановить отсортированный массив.

Пример:

2 5 3 2 8 5 2

Массив частот:

число: 0 1 2 3 4 5 6 7 8 частота: 0 0 3 1 0 2 0 0 1

Результат:

2 2 2 3 5 5 8

Сложность — O(n).

Ограничение: диапазон значений должен быть небольшим.

Выводы

  • Простые сортировки работают за O(n²).
  • Эффективные сортировки сравнениями работают за O(n log n).
  • Быстрее сортировать можно только при использовании дополнительной информации о данных.
  • В соревнованиях обычно используется стандартная сортировка (например, std::sort), реализующая алгоритм O(n log n).

В следующем разделе мы рассмотрим практическое использование сортировки в C++.