Алгоритмы сортировки
TL;DR
Сортировка — упорядочивание элементов по ключу. Все сравнительные сортировки (использующие только сравнения) подчиняются нижней границе [math]\displaystyle{ \Omega(n\log n) }[/math]: дерево решений содержит [math]\displaystyle{ n! }[/math] исходов-перестановок, значит глубина [math]\displaystyle{ \ge \log_2(n!) = \Theta(n\log n) }[/math]. Быстрее [math]\displaystyle{ n\log n }[/math] удаётся только не-сравнительным сортировкам — подсчётом ([math]\displaystyle{ O(n+k) }[/math]), поразрядно ([math]\displaystyle{ O(d(n+k)) }[/math]), карманной (среднее [math]\displaystyle{ O(n) }[/math]) — за счёт использования структуры ключей. Внутри класса [math]\displaystyle{ O(n\log n) }[/math] выбор определяется свойствами: устойчивость — слияние и Timsort, память [math]\displaystyle{ O(1) }[/math] — Пирамидальная сортировка, средняя скорость — Быстрая сортировка и introsort. Эта статья — обзор; детали каждого алгоритма — в отдельных статьях: Быстрая сортировка, Сортировка слиянием, Пирамидальная сортировка, Timsort.
| Свойство | Значение |
|---|---|
| Класс | Алгоритмы упорядочивания по ключу |
| Сравнительные | нижняя граница [math]\displaystyle{ \Omega(n\log n) }[/math] |
| Достижимо | [math]\displaystyle{ \Theta(n\log n) }[/math] в худшем: слияние, heapsort, Timsort |
| Быстрее | только не-сравнительные: подсчёт [math]\displaystyle{ O(n+k) }[/math], radix [math]\displaystyle{ O(d(n+k)) }[/math], bucket в среднем [math]\displaystyle{ O(n) }[/math] |
| Свойства | устойчивость, in-place, адаптивность, гарантия |
| Библиотеки | std::sort (introsort), std::stable_sort, Python (Timsort), Java (Timsort для объектов)
|
| Обозначения | [math]\displaystyle{ n }[/math] — число элементов, [math]\displaystyle{ k }[/math] — максимальное значение ключа (ключи [math]\displaystyle{ 0..k }[/math]), [math]\displaystyle{ d }[/math] — число разрядов |
| Связанные | Асимптотическая сложность, Амортизационный анализ |
Определения
Задача сортировки. Дан массив [math]\displaystyle{ a[1..n] }[/math] с ключами из линейно упорядоченного множества; требуется переставить элементы так, чтобы ключи не убывали: [math]\displaystyle{ a[1] \le a[2] \le \dots \le a[n] }[/math].
Сравнительная сортировка (comparison sort) — алгоритм, который получает информацию о ключах только через сравнения [math]\displaystyle{ a[i] \lessgtr a[j] }[/math]. К этому классу относятся quicksort, mergesort, heapsort, insertion sort и др.
Не-сравнительная сортировка — использует дополнительную структуру ключей (диапазон, разряды, распределение) и не считает сравнения как основную операцию: counting sort, radix sort, bucket sort.
Устойчивость (stability) — равные ключи сохраняют исходный взаимный порядок.
На месте (in-place) — алгоритм переставляет элементы в самом массиве, используя [math]\displaystyle{ O(1) }[/math] (или [math]\displaystyle{ O(\log n) }[/math] под рекурсию) памяти сверх входа.
Адаптивность — алгоритм ускоряется, если вход уже частично упорядочен.
Дерево решений (decision tree) — модель сравнительной сортировки: каждый внутренний узел — сравнение, каждый лист — результат (перестановка); высота дерева равна числу сравнений в худшем случае.
Нижняя граница [math]\displaystyle{ \Omega(n\log n) }[/math]. Любая сравнительная сортировка выполняет не менее [math]\displaystyle{ \lceil\log_2(n!)\rceil = \Theta(n\log n) }[/math] сравнений в худшем случае.
Обозначения. [math]\displaystyle{ n }[/math] — число элементов; [math]\displaystyle{ k }[/math] — максимальное значение ключа, то есть ключи лежат в [math]\displaystyle{ 0..k }[/math] ([math]\displaystyle{ k+1 }[/math] возможное значение); [math]\displaystyle{ d }[/math] — число разрядов; [math]\displaystyle{ \log }[/math] — двоичный. В bucket sort [math]\displaystyle{ k }[/math] — число карманов; это оговаривается отдельно.
Мотивация и интуиция
Сортировка — базовая операция: она ускоряет двоичный поиск, объединение (join в СУБД), отображение и дедупликацию; на отсортированных данных работают интервальные запросы к Дерево Фенвика. Вопрос «как быстро в принципе?» имеет точный ответ: сравнительные сортировки не могут быть быстрее [math]\displaystyle{ n\log n }[/math], и этот предел достигается (mergesort, heapsort). См. рис. 1 и рис. 2.
Ключевая идея нижней границы — подсчёт различимых исходов. Чтобы отсортировать [math]\displaystyle{ n }[/math] различных элементов, алгоритм должен уметь отличить любую из [math]\displaystyle{ n! }[/math] перестановок. Каждое сравнение даёт один бит информации (две ветви), поэтому дерево решений глубины [math]\displaystyle{ d }[/math] имеет не более [math]\displaystyle{ 2^d }[/math] листьев. Отсюда [math]\displaystyle{ 2^d \ge n! }[/math], то есть [math]\displaystyle{ d \ge \log_2(n!) = \Theta(n\log n) }[/math].
Обойти границу можно, выйдя за модель сравнений: если ключи — целые в диапазоне [math]\displaystyle{ 0..k }[/math], можно посчитать их частоты и разложить элементы без сравнений (counting sort); если ключи — мультиразрядные, сортировать по разрядам (radix); если равномерны — раскладывать по карманам (bucket).
Листья не обязаны лежать на одной глубине: часть из них может оказаться уже на глубине 2 (порядок определился после двух сравнений), но максимальная глубина дерева не меньше [math]\displaystyle{ \lceil\log_2 6\rceil = 3 }[/math] — именно она задаёт число сравнений в худшем случае.
Устройство
Сравнительные сортировки делятся на три группы по времени (см. рис. 1):
- [math]\displaystyle{ \Theta(n^2) }[/math]: вставками, выбором, пузырьком — простые, хороши на малых [math]\displaystyle{ n }[/math];
- [math]\displaystyle{ \Theta(n\log n) }[/math]: слиянием (устойчива, [math]\displaystyle{ O(n) }[/math] памяти), heapsort ([math]\displaystyle{ O(1) }[/math] памяти), Timsort (устойчива, адаптивна);
- быстрая: [math]\displaystyle{ O(n\log n) }[/math] в среднем, [math]\displaystyle{ \Theta(n^2) }[/math] в худшем (сводится к [math]\displaystyle{ O(n\log n) }[/math] в introsort).
Нижняя граница: доказательство (см. рис. 3)
Модель. Сортирующий алгоритм — это дерево решений: в каждом узле — сравнение двух элементов, две ветви соответствуют исходам. Листья — возможные результаты.
Доказательство. Для [math]\displaystyle{ n }[/math] различных ключей существует [math]\displaystyle{ n! }[/math] перестановок, и алгоритм обязан различать их (разным входам, требующим разного порядка, соответствуют разные листья). Двоичное дерево высоты [math]\displaystyle{ d }[/math] имеет не более [math]\displaystyle{ 2^d }[/math] листьев, поэтому [math]\displaystyle{ 2^d \ge n! }[/math], откуда [math]\displaystyle{ d \ge \log_2(n!) }[/math]. По формуле Стирлинга [math]\displaystyle{ n! \approx \sqrt{2\pi n}(n/e)^n }[/math], значит [math]\displaystyle{ \log_2(n!) = n\log_2 n - 1.44n + O(\log n) = \Theta(n\log n) }[/math]. [math]\displaystyle{ \square }[/math]
Следствие. Любой алгоритм из класса сравнений требует [math]\displaystyle{ \Omega(n\log n) }[/math] сравнений в худшем случае; алгоритмы слияния и heapsort достигают этой границы по порядку.
Как обойти границу (см. рис. 4)
Отказавшись от сравнений, получаем линейные (по [math]\displaystyle{ n }[/math]) сортировки при подходящих ключах:
- Counting sort: ключи [math]\displaystyle{ 0..k }[/math]; считаем частоты, строим префиксные суммы, раскладываем элементы на свои места. [math]\displaystyle{ O(n + k) }[/math].
- Radix sort (LSD): сортируем устойчиво по младшему разряду, затем по следующему. [math]\displaystyle{ O(d(n+k)) }[/math], где [math]\displaystyle{ d }[/math] — число разрядов.
- Bucket sort: равномерные ключи на [math]\displaystyle{ [0,1) }[/math]; раскладываем по карманам, каждый сортируем вставками. Среднее [math]\displaystyle{ O(n) }[/math].
Важно: эти сортировки не «нарушают» нижнюю границу — граница верна только для модели сравнений. Они получают информацию о ключах бесплатно (индексация, разряды), чего сравнительная модель не позволяет.
Операции и алгоритмы
Группа: квадратичные сортировки
Вставками. На каждом шаге вставляем a[i] в отсортированный префикс, сдвигая большие элементы. [math]\displaystyle{ O(n^2) }[/math] (в худшем), [math]\displaystyle{ O(n) }[/math] на почти отсортированных; устойчива, in-place. Хороша на малых [math]\displaystyle{ n }[/math] и как «хвост» гибридов.
Выбором. Находим минимум в остатке и ставим на место. [math]\displaystyle{ O(n^2) }[/math], мало обменов ([math]\displaystyle{ O(n) }[/math]), но неустойчива и не адаптивна.
Пузырьком. Обмены соседних «неправильных» пар. [math]\displaystyle{ O(n^2) }[/math]; учебный, на практике заменяется вставками.
Группа: [math]\displaystyle{ O(n\log n) }[/math]
- Слиянием (Сортировка слиянием): деление пополам и устойчивое слияние; гарантия [math]\displaystyle{ O(n\log n) }[/math], память [math]\displaystyle{ O(n) }[/math]; на списках — [math]\displaystyle{ O(\log n) }[/math].
- Пирамидальная (Пирамидальная сортировка): max-куча и извлечение максимума; [math]\displaystyle{ O(n\log n) }[/math] всегда при [math]\displaystyle{ O(1) }[/math] памяти; неустойчива.
- Быстрая (Быстрая сортировка): разбиение вокруг опорного; [math]\displaystyle{ O(n\log n) }[/math] в среднем, [math]\displaystyle{ \Theta(n^2) }[/math] в худшем; in-place, но неустойчива; introsort гарантирует [math]\displaystyle{ O(n\log n) }[/math].
- Timsort (Timsort): natural runs + слияние с инвариантом стека; лучший [math]\displaystyle{ O(n) }[/math], худший [math]\displaystyle{ O(n\log n) }[/math]; устойчива и адаптивна.
Группа: не-сравнительные
Counting sort (см. рис. 4):
Алгоритм Counting-Sort(a, k)
Вход: a[0..n−1], ключи — целые 0..k
Выход: out[0..n−1] — устойчиво отсортированная копия a
Инвариант: после шага 3 cnt[v] — число элементов ≤ v; перед итерацией шага 4
элементы a[n−1..i+1] уже размещены, а cnt[a[i]] указывает на
последнюю свободную позицию для ключа a[i]
Сложность: O(n + k) времени, O(n + k) памяти
Корректность: инвариант сохраняется на каждом шаге, см. раздел ниже
1 for v ← 0 to k: cnt[v] ← 0
2 for i ← 0 to n − 1: cnt[a[i]] ← cnt[a[i]] + 1
3 for v ← 1 to k: cnt[v] ← cnt[v] + cnt[v − 1] # префиксные суммы
4 for i ← n − 1 downto 0 # справа налево → устойчиво
5 cnt[a[i]] ← cnt[a[i]] − 1
6 out[cnt[a[i]]] ← a[i]
7 return out
Radix sort (LSD) (см. рис. 4):
- Пошагово: для каждого разряда, начиная с младшего, выполнить устойчивую counting-сортировку по этому разряду; основание [math]\displaystyle{ b }[/math] (обычно 256 — один байт); в формуле [math]\displaystyle{ O(d(n+k)) }[/math] символ [math]\displaystyle{ k }[/math] обозначает диапазон ключей.
- Сложность: [math]\displaystyle{ O(d(n+k)) }[/math] времени, [math]\displaystyle{ O(n+k) }[/math] памяти, где [math]\displaystyle{ d }[/math] — число разрядов.
- Крайние случаи: пустой массив и [math]\displaystyle{ n = 1 }[/math] — работа всё равно идёт по всем [math]\displaystyle{ d }[/math] разрядам; все ключи равны — [math]\displaystyle{ d }[/math] устойчивых проходов, порядок не меняется; [math]\displaystyle{ d }[/math] зависит от типа ключа (32-битный — 4 байта, 64-битный — 8), и при большом [math]\displaystyle{ d }[/math] поразрядная сортировка проигрывает сравнениям.
- Корректность: индукция по разрядам — устойчивость каждого прохода сохраняет порядок, установленный предыдущим (более младшим) разрядом.
Bucket sort (см. рис. 4):
- Пошагово: разложить элементы по [math]\displaystyle{ k }[/math] карманам по значению ключа, отсортировать каждый карман вставками, собрать карманы по порядку.
- Сложность: среднее [math]\displaystyle{ O(n) }[/math] при равномерных ключах (средний размер кармана [math]\displaystyle{ O(1) }[/math]), худшее [math]\displaystyle{ O(n^2) }[/math], память [math]\displaystyle{ O(n) }[/math].
- Крайние случаи: пустой массив; все ключи в одном кармане — сортировка вырождается в одну сортировку вставками, [math]\displaystyle{ O(n^2) }[/math]; сильно неравномерные ключи — карманы разного размера, оценка [math]\displaystyle{ O(n) }[/math] теряется.
- Устойчивость: сохраняется, если каждый карман отсортирован устойчиво и карманы собираются по возрастанию границ.
Сводная таблица сложности
| Алгоритм | Средний | Худший | Память | Устойчив | In-place | Адаптивен |
|---|---|---|---|---|---|---|
| Вставками | [math]\displaystyle{ O(n^2) }[/math] | [math]\displaystyle{ O(n^2) }[/math] | [math]\displaystyle{ O(1) }[/math] | да | да | да (O(n)) |
| Выбором | [math]\displaystyle{ O(n^2) }[/math] | [math]\displaystyle{ O(n^2) }[/math] | [math]\displaystyle{ O(1) }[/math] | нет | да | нет |
| Пузырьком | [math]\displaystyle{ O(n^2) }[/math] | [math]\displaystyle{ O(n^2) }[/math] | [math]\displaystyle{ O(1) }[/math] | да | да | да |
| Слиянием | [math]\displaystyle{ O(n\log n) }[/math] | [math]\displaystyle{ O(n\log n) }[/math] | [math]\displaystyle{ O(n) }[/math] | да | нет | слабо |
| Пирамидальная | [math]\displaystyle{ O(n\log n) }[/math] | [math]\displaystyle{ O(n\log n) }[/math] | [math]\displaystyle{ O(1) }[/math] | нет | да | нет |
| Быстрая | [math]\displaystyle{ O(n\log n) }[/math] | [math]\displaystyle{ O(n^2) }[/math] | [math]\displaystyle{ O(\log n) }[/math] | нет | да | слабо |
| Timsort | [math]\displaystyle{ O(n\log n) }[/math] | [math]\displaystyle{ O(n\log n) }[/math] | [math]\displaystyle{ O(n) }[/math] | да | нет | да (O(n)) |
| Подсчётом | [math]\displaystyle{ O(n+k) }[/math] | [math]\displaystyle{ O(n+k) }[/math] | [math]\displaystyle{ O(n+k) }[/math] | да | нет | нет |
| Radix (LSD) | [math]\displaystyle{ O(d(n+k)) }[/math] | [math]\displaystyle{ O(d(n+k)) }[/math] | [math]\displaystyle{ O(n+k) }[/math] | да | нет | нет |
| Bucket | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n^2) }[/math] | [math]\displaystyle{ O(n) }[/math] | да* | нет | нет |
Оговорки: *bucket sort устойчив, если карманы сортируются устойчиво и собираются по порядку. Не-сравнительные сортировки требуют предположений о ключах. Та же сводка в виде схемы — на рис. 5.
Трассировка примера
Трассировка counting sort. Вход [2a, 0b, 1c, 2d, 1e, 0f] — шесть элементов, ключи [math]\displaystyle{ 0..2 }[/math]:
| Шаг | Состояние cnt после шага |
out |
Комментарий |
|---|---|---|---|
| 2 | [2, 2, 2] |
— | частоты ключей 0, 1, 2 |
| 3 | [2, 4, 6] |
— | префиксные суммы: cnt[v] — число элементов [math]\displaystyle{ \le v }[/math]
|
| 4, [math]\displaystyle{ i = 5 }[/math] | [1, 4, 6] |
0f → позиция 1 |
ключ 0, правый из равных |
| 4, [math]\displaystyle{ i = 4 }[/math] | [1, 3, 6] |
1e → позиция 3 |
ключ 1 |
| 4, [math]\displaystyle{ i = 3 }[/math] | [1, 3, 5] |
2d → позиция 5 |
ключ 2, правый из равных |
| 4, [math]\displaystyle{ i = 2 }[/math] | [1, 2, 5] |
1c → позиция 2 |
ключ 1 |
| 4, [math]\displaystyle{ i = 1 }[/math] | [0, 2, 5] |
0b → позиция 0 |
ключ 0, левый из равных |
| 4, [math]\displaystyle{ i = 0 }[/math] | [0, 2, 4] |
2a → позиция 4 |
ключ 2, левый из равных |
Результат: 0b, 0f, 1c, 1e, 2a, 2d. Равные пары (0b, 0f), (1c, 1e), (2a, 2d) сохранили исходный порядок — устойчивость видна по шагам.
Эксперимент: число сравнений. Замерим число сравнений на массиве из [math]\displaystyle{ n = 4096 }[/math] случайных чисел из [math]\displaystyle{ 0..999999 }[/math] (seed 2024, код из «Служебного»; [math]\displaystyle{ n\log_2 n = 49\,152 }[/math]):
| Алгоритм | Сравнений | Отношение к [math]\displaystyle{ n\log_2 n }[/math] |
|---|---|---|
| Вставками | 4 227 948 | 86.0 |
| Слиянием | 43 950 | 0.894 |
| Пирамидальная | 85 605 | 1.74 |
| Быстрая (медиана трёх) | 58 703 | 1.19 |
| Подсчётом | 0 | — |
Вставки дают [math]\displaystyle{ \approx n^2/4 = 4\,194\,304 }[/math] сравнений (отношение 85.3), измерено 86.0 — оценка для случайного входа выполняется. На этом прогоне нижняя граница выполнена у всех сравнительных сортировок: [math]\displaystyle{ \log_2(n!) \approx 43\,250 }[/math], а минимум по таблице — 43 950 у слияния. Сама граница — про худший случай, а не про каждый вход: на уже отсортированном массиве вставки делают всего [math]\displaystyle{ n-1 }[/math] сравнение. Counting sort делает ноль сравнений элементов (использует ключи как индексы). Значения измерены кодом из «Служебного» (seed 2024); нижняя граница проверяется assert'ом.
Корректность и оценка сложности
Нижняя граница
Доказана выше через дерево решений: [math]\displaystyle{ d \ge \log_2(n!) = \Theta(n\log n) }[/math]. Более точная оценка с константами: [math]\displaystyle{ \log_2(n!) = n\log_2 n - 1.44n + O(\log n) }[/math].
Достижимость
Сортировка слиянием делает [math]\displaystyle{ T(n) = 2T(n/2) + \Theta(n) = \Theta(n\log n) }[/math] сравнений (см. Сортировка слиянием); heapsort — не более [math]\displaystyle{ 2n\log_2 n }[/math]; Timsort сохраняет [math]\displaystyle{ O(n\log n) }[/math]. Значит, граница достижима по порядку, и класс [math]\displaystyle{ O(n\log n) }[/math] для сравнений оптимален.
Корректность counting sort
После шага 3 cnt[v] — число элементов [math]\displaystyle{ \le v }[/math], поэтому ключ [math]\displaystyle{ v }[/math] занимает позиции cnt[v-1]..cnt[v]-1 (для [math]\displaystyle{ v = 0 }[/math] — от нуля). Проход справа налево и уменьшение счётчика сохраняют исходный порядок равных: первый равный элемент исходного массива получает меньшую позицию, второй — следующую, и т.д. Поэтому сортировка устойчива. После всех [math]\displaystyle{ n }[/math] шагов каждый элемент на своём месте. [math]\displaystyle{ \square }[/math]
Трассировка. Вход [math]\displaystyle{ [(2,a), (1,b), (2,c), (0,d)] }[/math]: частоты cnt = [1, 1, 2], после префиксных сумм cnt = [1, 2, 4]. Проход справа налево: (2,c) → позиция 3, (0,d) → позиция 0, (1,b) → позиция 1, (2,a) → позиция 2. Выход: 0d, 1b, 2a, 2c — равные 2a и 2c сохранили исходный порядок.
Radix sort (LSD)
Каждый разряд обрабатывается устойчивой counting-сортировкой; индукция по разрядам (LSD) гарантирует правильный порядок после старшего разряда.
Сравнение с альтернативами
| Критерий выбора | Что брать |
|---|---|
| Нужна устойчивость | Сортировка слиянием, Timsort, вставками, подсчётом |
| Нужна память [math]\displaystyle{ O(1) }[/math] | Пирамидальная сортировка, вставками |
| Нужна максимальная средняя скорость | Быстрая сортировка / introsort |
| Нужна адаптивность | Timsort |
| Нужна гарантия [math]\displaystyle{ O(n\log n) }[/math] | Сортировка слиянием, Пирамидальная сортировка, introsort |
| Целые ключи, малый диапазон | counting sort, radix |
| Равномерные ключи | bucket sort |
Независимые свойства. Устойчивость, in-place, адаптивность и гарантия не связаны: нельзя получить всё сразу. Например, mergesort устойчив и гарантирован, но платит [math]\displaystyle{ O(n) }[/math] памяти; heapsort экономит память, но неустойчив (см. рис. 6).
Где применяется
Практический выбор диктуют свойства сортировки, а не только асимптотика (см. рис. 7).
- Стандартные библиотеки.
std::sort(introsort — скорость и гарантия),std::stable_sort(адаптивное слияние), Pythonsorted/list.sort(Timsort), JavaArrays.sort(dual-pivot quicksort для примитивов, Timsort для объектов). Почему: разные требования к устойчивости и памяти [1][5].
- Системы реального времени и embedded. heapsort ([math]\displaystyle{ O(1) }[/math] памяти, гарантия) или сортировка вставками на малых данных. Почему: нельзя допустить худшего [math]\displaystyle{ \Theta(n^2) }[/math] и лишних буферов [2].
- Большие данные и внешняя сортировка. Слияние и многопутевое слияние: данные на диске, важен последовательный доступ. Почему: слияние линейно и последовательно [2][3].
- Целые/короткие фиксированные ключи. Counting и radix в гистограммах, кодировании, биоинформатике (сортировка последовательностей по суффиксам/префиксам). Почему: [math]\displaystyle{ O(n+k) }[/math] быстрее сравнений [1][5].
- СУБД и аналитика. Sort-merge join, агрегации, оконные функции опираются на устойчивую сортировку и внешнее слияние. Почему: устойчивость и предсказуемость [3].
Историческая справка
Сортировки — старейшая область алгоритмов. Пузырьковая сортировка и сортировка вставками известны с первых лет вычислений; Shellsort предложил Дональд Шелл в 1959 году [5] (обобщение вставок с шагами). Быструю сортировку изобрёл Тони Хоар (1961–1962) [6]; пирамидальную — Дж. Уильямс (1964) с линейным build-heap Р. Флойда (1964) [7]; слияние восходит к Джону фон Нейману (1945) [2]. Не-сравнительные сортировки уходят корнями в перфокарточные машины Холлерита (radix-сортировка, конец XIX века) и counting sort [5].
Нижняя граница [math]\displaystyle{ \Omega(n\log n) }[/math] через деревья решений — классический результат информационной теории; подробное изложение — Кнут, т. 3 [5], и CLRS, гл. 8 (сортировка за линейное время и нижняя граница) [1].
Типичные ошибки и подводные камни
- Ожидание линейного времени от сравнительных сортировок. Невозможно (нижняя граница); [math]\displaystyle{ O(n) }[/math] достижим только вне модели сравнений.
- Применение counting/radix к произвольным ключам. Нужны целые/ограниченный диапазон; иначе [math]\displaystyle{ k }[/math] велик, и сортировка медленна.
- Неустойчивость там, где нужна устойчивость. Сортировка по составным ключам требует устойчивого алгоритма (mergesort/Timsort), а не quicksort/heapsort.
- Игнорирование памяти. mergesort/Timsort требуют [math]\displaystyle{ O(n) }[/math]; в embedded берут heapsort.
- Худший случай quicksort. На «анти-входах» — [math]\displaystyle{ \Theta(n^2) }[/math]; рандомизация снижает вероятность такого входа, а introsort даёт гарантию [math]\displaystyle{ O(n\log n) }[/math].
- Переполнение ключей в counting. Диапазон [math]\displaystyle{ k }[/math] и счётчики должны помещаться в тип.
- Путаница [math]\displaystyle{ O(n) }[/math] и [math]\displaystyle{ O(n+k) }[/math]. Если [math]\displaystyle{ k \gg n }[/math], counting/radix проигрывают сравнениям.
- Смешение 0- и 1-базной индексации в counting (позиции
cnt[a[i]] - 1). - Сортировка маленьких массивов «тяжёлым» алгоритмом. На [math]\displaystyle{ n \lt 16 }[/math] вставки быстрее; гибриды так и делают.
- Stable vs in-place trade-off. Для [math]\displaystyle{ O(n\log n) }[/math]-сортировок в худшем случае устойчивость обычно требует [math]\displaystyle{ O(n) }[/math] памяти, а in-place-версии обычно неустойчивы; совмещать оба свойства дёшево не получается. У квадратичных сортировок (вставки, пузырёк) оба свойства есть, но за счёт времени.
Задачи для практики
- Нижняя граница. Докажите, что любая сравнительная сортировка делает [math]\displaystyle{ \Omega(n\log n) }[/math] сравнений. Подсказка: дерево решений и [math]\displaystyle{ n! }[/math].
- Counting sort. Реализуйте устойчивую сортировку подсчётом и проверьте на дубликатах. Подсказка: проход справа налево.
- Radix. Отсортируйте 32-битные числа поразрядно и сравните время с
std::sort. Подсказка: 4 прохода по байтам.
- Устойчивость. Определите, какие из quicksort/heapsort/mergesort/Timsort устойчивы, и приведите контрпример для неустойчивого.
- Худший вход. Постройте вход, дающий quicksort [math]\displaystyle{ \Theta(n^2) }[/math], и проверьте подсчётом.
- Гибрид. Скомбинируйте quicksort и сортировку вставками при [math]\displaystyle{ n \lt 16 }[/math]; сравните число сравнений.
- Выбор. Для задачи «устойчиво отсортировать по двум ключам» выберите алгоритм и объясните. Подсказка: сначала по второстепенному, затем устойчиво по главному.
- Оценка ключей. Когда counting sort быстрее mergesort? Выведите условие через [math]\displaystyle{ k }[/math] и [math]\displaystyle{ n }[/math]. Подсказка: [math]\displaystyle{ n + k }[/math] против [math]\displaystyle{ n\log n }[/math].
Ответы и оценки сложности.
- Двоичное дерево глубины [math]\displaystyle{ d }[/math] имеет не более [math]\displaystyle{ 2^d }[/math] листьев, а различимых исходов [math]\displaystyle{ n! }[/math]; значит, [math]\displaystyle{ 2^d \ge n! }[/math] и [math]\displaystyle{ d \ge \log_2(n!) = \Theta(n\log n) }[/math].
out[--cnt[key]]при проходе справа налево; время [math]\displaystyle{ O(n+k) }[/math], память [math]\displaystyle{ O(n+k) }[/math], сравнений нет. На[(2,a),(2,b)]выход2a, 2b— порядок сохранён.- Четыре прохода по байтам (32 бита = 4 × 8), время [math]\displaystyle{ O(4(n+256)) }[/math] — линейно по [math]\displaystyle{ n }[/math], но с большой константой; на малых [math]\displaystyle{ n }[/math] radix проигрывает из-за накладных расходов.
- Устойчивы mergesort и Timsort; quicksort и heapsort — нет. Контрпример:
[(1,a),(1,b),(0,c)]при опорном(1,b)quicksort может поставитьbпередa. - Уже отсортированный (или обратно отсортированный) массив при опорном «первый элемент» даёт [math]\displaystyle{ n(n-1)/2 }[/math] сравнений, то есть [math]\displaystyle{ \Theta(n^2) }[/math].
- Время остаётся [math]\displaystyle{ \Theta(n\log n) }[/math] в среднем, но на коротких отрезках вставки делают не больше [math]\displaystyle{ O(m^2) }[/math] сравнений при [math]\displaystyle{ m \lt 16 }[/math] — это дешевле рекурсии; конкретный выигрыш зависит от констант ⚠️ требует проверки на вашей машине.
- Сначала устойчиво по второстепенному ключу, затем устойчиво по главному — два прохода [math]\displaystyle{ O(n\log n) }[/math]; если ключи целые и малы, дешевле counting sort по главному на втором проходе.
- [math]\displaystyle{ n + k \lt n\log_2 n }[/math], то есть примерно [math]\displaystyle{ k \lt n(\log_2 n - 1) }[/math]; иначе [math]\displaystyle{ k }[/math] велик и counting проигрывает mergesort.
Связанные темы
- Быстрая сортировка — средняя скорость, introsort.
- Сортировка слиянием — устойчивость и гарантия.
- Пирамидальная сортировка — гарантия при [math]\displaystyle{ O(1) }[/math] памяти.
- Сортировка вставками — база гибридов; адаптивность и малые массивы.
- Сортировка Шелла, Сортировка выбором, Сортировка пузырьком — элементарные сортировки-родственники.
- Timsort — адаптивность и устойчивость.
- Асимптотическая сложность — нижние границы и рекуррентности.
- Графы — многие графовые задачи начинаются с сортировки рёбер/вершин.
Источники
- Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 2, 6, 7, 8 (mergesort, heapsort, quicksort, сортировка за линейное время и нижняя граница).
- Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — Гл. 2 (сортировки), приложения к внешней сортировке.
- Silberschatz A., Korth H. F., Sudarshan S. Database System Concepts. — McGraw-Hill, 7th ed., 2019 (внешняя сортировка, sort-merge join).
- Peters T. listsort.txt (Timsort). URL: https://github.com/python/cpython/blob/main/Objects/listsort.txt.
- Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998 (алгоритмы, нижние границы, radix, внешняя сортировка) .
- Hoare C. A. R. Quicksort // The Computer Journal. — 1962. — Vol. 5, № 1.
- Williams J. W. J. Algorithm 232: Heapsort // CACM. — 1964; Floyd R. W. Algorithm 245: Treesort // CACM. — 1964.
- Wikipedia: Sorting algorithm. URL: https://en.wikipedia.org/wiki/Sorting_algorithm.