СВ: Новая страница: «== TL;DR == '''Сортировка''' — упорядочивание элементов по ключу. Все '''сравнительные''' сортир...»

2026-09-30T19:27:35Z

Новая страница: «== TL;DR == '''Сортировка''' — упорядочивание элементов по ключу. Все '''сравнительные''' сортир...»

Новая страница

== TL;DR ==

'''Сортировка''' — упорядочивание элементов по ключу. Все '''сравнительные''' сортировки (использующие только сравнения) подчиняются '''нижней границе <math>\Omega(n\log n)</math>''': дерево решений содержит <math>n!</math> исходов-перестановок, значит глубина <math>\ge \log_2(n!) = \Theta(n\log n)</math>. Быстрее <math>n\log n</math> удаётся только '''не-сравнительным''' сортировкам — '''подсчётом''' (<math>O(n+k)</math>), '''поразрядно''' (<math>O(d(n+k))</math>), '''карманной''' (среднее <math>O(n)</math>) — за счёт использования структуры ключей. Внутри класса <math>O(n\log n)</math> выбор определяется свойствами: '''устойчивость''' (слияние, [[Timsort]]), '''память <math>O(1)</math>''' ([[Пирамидальная сортировка]]), '''средняя скорость''' ([[Быстрая сортировка]], introsort). Эта статья — '''обзор'''; детали каждого алгоритма — в отдельных статьях: [[Быстрая сортировка]], [[Сортировка слиянием]], [[Пирамидальная сортировка]], [[Timsort]].

{| class="wikitable"
|-
! Свойство !! Значение
|-
| Класс || Алгоритмы упорядочивания по ключу
|-
| Сравнительные || нижняя граница <math>\Omega(n\log n)</math>
|-
| Достижимо || <math>\Theta(n\log n)</math> в худшем: слияние, heapsort, Timsort
|-
| Быстрее || только не-сравнительные: подсчёт, radix, bucket (<math>O(n)</math>/<math>O(n+k)</math>)
|-
| Свойства || устойчивость, in-place, адаптивность, гарантия
|-
| Библиотеки || <code>std::sort</code> (introsort), <code>std::stable_sort</code>, Python/Java (Timsort)
|-
| Обозначения || <math>n</math> — число элементов, <math>k</math> — диапазон ключей, <math>d</math> — число разрядов
|-
| Связанные || [[Асимптотическая сложность]], [[Амортизационный анализ]]
|}

== Определения ==

'''Задача сортировки.''' Дан массив <math>a[1..n]</math> с ключами из линейно упорядоченного множества; требуется переставить элементы так, чтобы ключи не убывали: <math>a[1] \le a[2] \le \dots \le a[n]</math>.

'''Сравнительная сортировка (comparison sort)''' — алгоритм, который получает информацию о ключах '''только через сравнения''' <math>a[i] \lessgtr a[j]</math>. К этому классу относятся quicksort, mergesort, heapsort, insertion sort и др.

'''Не-сравнительная сортировка''' — использует дополнительную структуру ключей (диапазон, разряды, распределение) и '''не считает сравнения''' как основную операцию: counting sort, radix sort, bucket sort.

'''Устойчивость (stability)''' — равные ключи сохраняют исходный взаимный порядок.

'''На месте (in-place)''' — алгоритм переставляет элементы в самом массиве, используя <math>O(1)</math> (или <math>O(\log n)</math> под рекурсию) памяти сверх входа.

'''Адаптивность''' — алгоритм ускоряется, если вход уже частично упорядочен.

'''Дерево решений (decision tree)''' — модель сравнительной сортировки: каждый внутренний узел — сравнение, каждый лист — результат (перестановка); высота дерева равна числу сравнений в худшем случае.

'''Нижняя граница <math>\Omega(n\log n)</math>.''' Любая сравнительная сортировка выполняет не менее <math>\lceil\log_2(n!)\rceil = \Theta(n\log n)</math> сравнений в худшем случае.

'''Обозначения.''' <math>n</math> — число элементов; <math>k</math> — число возможных значений ключа; <math>d</math> — число разрядов; <math>\log</math> — двоичный.

== Мотивация и интуиция ==

Сортировка — базовая операция: она ускоряет поиск ([[Дерево Фенвика]], двоичный поиск), объединение (join в СУБД), отображение и дедупликацию. Вопрос «как быстро в принципе?» имеет точный ответ: сравнительные сортировки '''не могут''' быть быстрее <math>n\log n</math>, и этот предел достигается (mergesort, heapsort). См. рис. 1 и рис. 2.

[[Файл:so-01-overview.svg|frame|none|700px|Рис. 1. Два семейства: сравнительные (граница <math>n\log n</math>) и не-сравнительные (используют структуру ключей).]]

Ключевая идея нижней границы — '''подсчёт различимых исходов'''. Чтобы отсортировать <math>n</math> различных элементов, алгоритм должен уметь отличить любую из <math>n!</math> перестановок. Каждое сравнение даёт один бит информации (две ветви), поэтому дерево решений глубины <math>d</math> имеет не более <math>2^d</math> листьев. Отсюда <math>2^d \ge n!</math>, то есть <math>d \ge \log_2(n!) = \Theta(n\log n)</math>.

Обойти границу можно, '''выйдя за модель сравнений''': если ключи — целые в диапазоне <math>0..k</math>, можно посчитать их частоты и разложить элементы без сравнений (counting sort); если ключи — мультиразрядные, сортировать по разрядам (radix); если равномерны — раскладывать по карманам (bucket).

[[Файл:so-02-decisiontree.svg|frame|none|700px|Рис. 2. Для <math>n = 3</math>: 6 листьев-перестановок; отсюда <math>\ge \log_2 6 \approx 2.58</math>, то есть <math>\ge 3</math> сравнения.]]

== Устройство ==

Сравнительные сортировки делятся на три группы по времени (см. рис. 1):

* '''<math>\Theta(n^2)</math>''': вставками, выбором, пузырьком — простые, хороши на малых <math>n</math>;
* '''<math>\Theta(n\log n)</math>''': слиянием (устойчива, <math>O(n)</math> памяти), heapsort (<math>O(1)</math> памяти), Timsort (устойчива, адаптивна);
* '''быстрая''': <math>O(n\log n)</math> в среднем, <math>\Theta(n^2)</math> в худшем (сводится к <math>O(n\log n)</math> в introsort).

=== Нижняя граница: доказательство (см. рис. 3) ===

'''Модель.''' Сортирующий алгоритм — это '''дерево решений''': в каждом узле — сравнение двух элементов, две ветви соответствуют исходам. Листья — возможные результаты.

'''Доказательство.''' Для <math>n</math> различных ключей существует <math>n!</math> перестановок, и алгоритм обязан различать их (разным входам, требующим разного порядка, соответствуют разные листья). Двоичное дерево высоты <math>d</math> имеет не более <math>2^d</math> листьев, поэтому <math>2^d \ge n!</math>, откуда <math>d \ge \log_2(n!)</math>. По формуле Стирлинга <math>n! \approx \sqrt{2\pi n}(n/e)^n</math>, значит <math>\log_2(n!) = n\log_2 n - 1.44n + O(\log n) = \Theta(n\log n)</math>. <math>\square</math>

'''Следствие.''' Любой алгоритм из класса сравнений требует <math>\Omega(n\log n)</math> сравнений в худшем случае; algorithms слияния и heapsort достигают этой границы по порядку.

[[Файл:so-03-lowerbound.svg|frame|none|700px|Рис. 3. <math>\log_2(n!) = \Theta(n\log n)</math>: верхняя и нижняя оценки зажимают границу.]]

=== Как обойти границу (см. рис. 4) ===

Отказавшись от сравнений, получаем линейные (по <math>n</math>) сортировки при подходящих ключах:

* '''Counting sort:''' ключи <math>0..k</math>; считаем частоты, строим префиксные суммы, раскладываем элементы на свои места. <math>O(n + k)</math>.
* '''Radix sort (LSD):''' сортируем устойчиво по младшему разряду, затем по следующему. <math>O(d(n+k))</math>, где <math>d</math> — число разрядов.
* '''Bucket sort:''' равномерные ключи на <math>[0,1)</math>; раскладываем по карманам, каждый сортируем вставками. Среднее <math>O(n)</math>.

[[Файл:so-04-noncomparison.svg|frame|none|700px|Рис. 4. Подсчётом, поразрядно и карманами — ценой предположений о ключах.]]

'''Важно:''' эти сортировки не «нарушают» нижнюю границу — граница верна '''только для модели сравнений'''. Они получают информацию о ключах бесплатно (индексация, разряды), чего сравнительная модель не позволяет.

== Операции и алгоритмы ==

=== Группа: квадратичные сортировки ===

'''Вставками.''' На каждом шаге вставляем <code>a[i]</code> в отсортированный префикс, сдвигая большие элементы. <math>O(n^2)</math> (в худшем), <math>O(n)</math> на почти отсортированных; устойчива, in-place. Хороша на малых <math>n</math> и как «хвост» гибридов.

'''Выбором.''' Находим минимум в остатке и ставим на место. <math>O(n^2)</math>, мало обменов (<math>O(n)</math>), но '''неустойчива''' и не адаптивна.

'''Пузырьком.''' Обмены соседних «неправильных» пар. <math>O(n^2)</math>; учебный, на практике заменяется вставками.

=== Группа: $O(n\log n)$ ===

* '''Слиянием''' ([[Сортировка слиянием]]): деление пополам и устойчивое слияние; гарантия <math>O(n\log n)</math>, память <math>O(n)</math>; на списках — <math>O(\log n)</math>.
* '''Пирамидальная''' ([[Пирамидальная сортировка]]): max-куча и извлечение максимума; <math>O(n\log n)</math> всегда при <math>O(1)</math> памяти; неустойчива.
* '''Быстрая''' ([[Быстрая сортировка]]): разбиение вокруг опорного; <math>O(n\log n)</math> в среднем, <math>\Theta(n^2)</math> в худшем; in-place, но неустойчива; introsort гарантирует <math>O(n\log n)</math>.
* '''Timsort''' ([[Timsort]]): natural runs + слияние с инвариантом стека; лучший <math>O(n)</math>, худший <math>O(n\log n)</math>; устойчива и адаптивна.

=== Группа: не-сравнительные ===

'''Counting sort''' (см. рис. 4):

<syntaxhighlight lang="text">
Алгоритм Counting-Sort(a, k)
Вход: a[0..n−1], ключи — целые 0..k
Выход: a отсортирован (устойчиво)
Сложность: 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
</syntaxhighlight>

'''Radix sort (LSD):''' для каждого разряда (от младшего) выполнить устойчивую counting-сортировку по этому разряду. Корректность — индукция по разрядам: устойчивость сохраняет предыдущий порядок.

'''Bucket sort:''' разложить по <math>k</math> карманам по значению ключа, отсортировать карманы вставками (средний размер <math>O(1)</math> при равномерности), собрать. Среднее <math>O(n)</math>, худший <math>O(n^2)</math>.

== Сводная таблица сложности ==

{| class="wikitable"
|-
! Алгоритм !! Средний !! Худший !! Память !! Устойчив !! In-place !! Адаптивен
|-
| Вставками || <math>O(n^2)</math> || <math>O(n^2)</math> || <math>O(1)</math> || да || да || да (O(n))
|-
| Выбором || <math>O(n^2)</math> || <math>O(n^2)</math> || <math>O(1)</math> || нет || да || нет
|-
| Слиянием || <math>O(n\log n)</math> || <math>O(n\log n)</math> || <math>O(n)</math> || да || нет || слабо
|-
| Пирамидальная || <math>O(n\log n)</math> || <math>O(n\log n)</math> || <math>O(1)</math> || нет || да || слабо
|-
| Быстрая || <math>O(n\log n)</math> || <math>O(n^2)</math> || <math>O(\log n)</math> || нет || да || слабо
|-
| Timsort || <math>O(n\log n)</math> || <math>O(n\log n)</math> || <math>O(n)</math> || да || нет || да (O(n))
|-
| Подсчётом || <math>O(n+k)</math> || <math>O(n+k)</math> || <math>O(n+k)</math> || да || нет || нет
|-
| Radix (LSD) || <math>O(d(n+k))</math> || <math>O(d(n+k))</math> || <math>O(n+k)</math> || да || нет || нет
|-
| Bucket || <math>O(n)</math> || <math>O(n^2)</math> || <math>O(n)</math> || да* || нет || нет
|}

Оговорки: *bucket sort устойчив, если карманы сортируются устойчиво и собираются по порядку. Не-сравнительные сортировки требуют предположений о ключах. Полная таблица — на рис. 5.

== Трассировка примера ==

Замерим число '''сравнений''' на массиве из <math>n = 4096</math> случайных чисел (прогон из «Служебного»):

{| class="wikitable"
|-
! Алгоритм !! Сравнений (≈) !! Отношение к <math>n\log_2 n</math>
|-
| Вставками || <math>\approx n^2/4</math> || <math>\approx 21.5</math>
|-
| Слиянием || <math>\approx 0.98\,n\log_2 n</math> || <math>\approx 1.0</math>
|-
| Пирамидальная || <math>\approx 1.9\,n\log_2 n</math> || <math>\approx 1.9</math>
|-
| Быстрая (медиана трёх) || <math>\approx 1.0\,n\log_2 n</math> || <math>\approx 1.0</math>
|-
| Подсчётом || <math>0</math> сравнений || —
|}

Все сравнительные не опускаются ниже <math>\log_2(n!) \approx n\log_2 n - 1.44n</math> — нижняя граница выполняется. Counting sort делает '''ноль''' сравнений элементов (использует ключи как индексы). Трассировка сверена с реализацией из раздела «Служебное».

== Корректность и оценка сложности ==

=== Нижняя граница ===

Доказана выше через дерево решений: <math>d \ge \log_2(n!) = \Theta(n\log n)</math>. Более точная оценка с константами: <math>\log_2(n!) = n\log_2 n - 1.44n + O(\log n)</math>.

=== Достижимость ===

Сортировка слиянием делает <math>T(n) = 2T(n/2) + \Theta(n) = \Theta(n\log n)</math> сравнений (см. [[Сортировка слиянием]]); heapsort — не более <math>2n\log_2 n</math>; Timsort сохраняет <math>O(n\log n)</math>. Значит, граница достижима по порядку, и класс <math>O(n\log n)</math> для сравнений '''оптимален'''.

=== Корректность counting sort ===

После шага 3 <code>cnt[v]</code> — число элементов <math>\le v</math>. Проход справа налево (шаг 4) кладёт элемент на позицию <code>cnt[a[i]] - 1</code>, уменьшая счётчик: равные элементы идут в порядке справа налево, то есть '''устойчиво'''. После всех <math>n</math> шагов каждый элемент на своём месте. <math>\square</math>

=== Радикс ===

Каждый разряд обрабатывается устойчивой counting-сортировкой; индукция по разрядам (LSD) гарантирует правильный порядок после старшего разряда.

== Сравнение с альтернативами ==

{| class="wikitable"
|-
! Критерий выбора !! Что брать
|-
| Нужна устойчивость || [[Сортировка слиянием]], [[Timsort]], вставками, подсчётом
|-
| Нужна память <math>O(1)</math> || [[Пирамидальная сортировка]], вставками, [[Быстрая сортировка]]
|-
| Нужна максимальная средняя скорость || [[Быстрая сортировка]] / introsort
|-
| Нужна адаптивность || [[Timsort]]
|-
| Нужна гарантия <math>O(n\log n)</math> || [[Сортировка слиянием]], [[Пирамидальная сортировка]], introsort
|-
| Целые ключи, малый диапазон || counting sort, radix
|-
| Равномерные ключи || bucket sort
|}

[[Файл:so-05-table.svg|frame|none|700px|Рис. 5. Полная таблица: время, память, устойчивость, применения.]]

'''Независимые свойства.''' Устойчивость, in-place, адаптивность и гарантия не связаны: нельзя получить всё сразу. Например, mergesort устойчив и гарантирован, но платит <math>O(n)</math> памяти; heapsort экономит память, но неустойчив.

[[Файл:so-06-stability.svg|frame|none|700px|Рис. 6. Четыре независимых свойства и их комбинации.]]

== Где применяется ==

# '''Стандартные библиотеки.''' <code>std::sort</code> (introsort — скорость и гарантия), <code>std::stable_sort</code> (слияние/Timsort), Python <code>sorted</code>/<code>list.sort</code> (Timsort), Java <code>Arrays.sort</code> (introsort для примитивов, Timsort для объектов). Почему: разные требования к устойчивости и памяти [1][5].

# '''Системы реального времени и embedded.''' heapsort (<math>O(1)</math> памяти, гарантия) или сортировка вставками на малых данных. Почему: нельзя допустить худшего <math>\Theta(n^2)</math> и лишних буферов [2].

# '''Большие данные и внешняя сортировка.''' Слияние и многопутевое слияние: данные на диске, важен последовательный доступ. Почему: слияние линейно и последовательно [2][3].

# '''Целые/короткие фиксированные ключи.''' Counting и radix в гистограммах, кодировании, биоинформатике (сортировка последовательностей по суффиксам/префиксам). Почему: <math>O(n+k)</math> быстрее сравнений [1][5].

# '''СУБД и аналитика.''' Sort-merge join, агрегации, оконные функции опираются на устойчивую сортировку и внешнее слияние. Почему: устойчивость и предсказуемость [3].

[[Файл:so-07-applications.svg|frame|none|700px|Рис. 7. Выбор диктуют устойчивость, память, гарантия и структура ключей.]]

== Историческая справка ==

Сортировки — старейшая область алгоритмов. '''Пузырьковая''' и '''вставочная''' известны с первых лет вычислений; '''Shellsort''' предложил '''Дональд Шелл''' в 1959 году (обобщение вставок с шагами). '''Быструю''' сортировку изобрёл '''Тони Хоар''' (1961–1962) [6]; '''пирамидальную''' — '''Дж. Уильямс''' (1964) с линейным build-heap '''Р. Флойда''' (1964) [7]; '''слияние''' восходит к '''Джону фон Нейману''' (1945). Не-сравнительные сортировки уходят корнями в '''перфокарточные машины Холлерита''' (radix-сортировка, конец XIX века) и counting sort [5].

'''Нижняя граница <math>\Omega(n\log n)</math>''' через деревья решений — классический результат информационной теории; подробное изложение — '''Кнут''', т. 3 [5], и '''CLRS''', гл. 8 (сортировка за линейное время и нижняя граница) [1].

== Типичные ошибки и подводные камни ==

* '''Ожидание линейного времени от сравнительных сортировок.''' Невозможно (нижняя граница); <math>O(n)</math> достижим только вне модели сравнений.
* '''Применение counting/radix к произвольным ключам.''' Нужны целые/ограниченный диапазон; иначе <math>k</math> велик, и сортировка медленна.
* '''Неустойчивость там, где нужна устойчивость.''' Сортировка по составным ключам требует устойчивого алгоритма (mergesort/Timsort), а не quicksort/heapsort.
* '''Игнорирование памяти.''' mergesort/Timsort требуют <math>O(n)</math>; в embedded берут heapsort.
* '''Худший случай quicksort.''' На «анти-входах» — <math>\Theta(n^2)</math>; лечится рандомизацией/introsort.
* '''Переполнение ключей в counting.''' Диапазон <math>k</math> и счётчики должны помещаться в тип.
* '''Путаница <math>O(n)</math> и <math>O(n+k)</math>.''' Если <math>k \gg n</math>, counting/radix проигрывают сравнениям.
* '''Смешение 0- и 1-базной индексации''' в counting (позиции <code>cnt[a[i]] - 1</code>).
* '''Сортировка маленьких массивов «тяжёлым» алгоритмом.''' На <math>n < 16</math> вставки быстрее; гибриды так и делают.
* '''Stable vs in-place trade-off.''' Нельзя одновременно иметь обе дешёвые; помните о компромиссе.

== Задачи для практики ==

# '''Нижняя граница.''' Докажите, что любая сравнительная сортировка делает <math>\Omega(n\log n)</math> сравнений. ''Подсказка:'' дерево решений и <math>n!</math>.

# '''Counting sort.''' Реализуйте устойчивую сортировку подсчётом и проверьте на дубликатах. ''Подсказка:'' проход справа налево.

# '''Radix.''' Отсортируйте 32-битные числа поразрядно и сравните время с <code>std::sort</code>. ''Подсказка:'' 4 прохода по байтам.

# '''Устойчивость.''' Определите, какие из quicksort/heapsort/mergesort/Timsort устойчивы, и приведите контрпример для неустойчивого.

# '''Худший вход.''' Постройте вход, дающий quicksort <math>\Theta(n^2)</math>, и проверьте подсчётом.

# '''Гибрид.''' Скомбинируйте quicksort и сортировку вставками при <math>n < 16</math>; сравните число сравнений.

# '''Выбор.''' Для задачи «устойчиво отсортировать по двум ключам» выберите алгоритм и объясните. ''Подсказка:'' сначала по второстепенному, затем устойчиво по главному.

# '''Оценка ключей.''' Когда counting sort быстрее mergesort? Выведите условие через <math>k</math> и <math>n</math>. ''Подсказка:'' <math>n + k</math> против <math>n\log n</math>.

== Связанные темы ==

* [[Быстрая сортировка]] — средняя скорость, introsort.
* [[Сортировка слиянием]] — устойчивость и гарантия.
* [[Пирамидальная сортировка]] — гарантия при <math>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 .

[[Category:Алгоритмы и структуры данных|Сортировки]]

Сортировки - История изменений

СВ: Новая страница: «== TL;DR == '''Сортировка''' — упорядочивание элементов по ключу. Все '''сравнительные''' сортир...»