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

Карта раздела

Раздел отвечает на вопрос «как упорядочить данные и какую сортировку выбрать». Пять глав - от простых квадратов к оптимуму и за его предел.

простые (Θ(n²))      ->  вставками адаптивна и устойчива; выбором дёшев по обменам
     |
слияние и быстрая    ->  два n·log n: гарантия+память vs на месте+худший случай
     |
пирамидальная        ->  n·log n на месте (куча за Θ(n)); страховка introsort
     |
нижняя граница       ->  сравнениями быстрее n·log n нельзя; подсчёт/поразрядная - за линию
     |
на практике          ->  устойчивость, многоключевость, Timsort/introsort, выбор под данные

Сводная таблица сортировок

Главный итог раздела - по трём осям: время, память, устойчивость.

сортировка	среднее	худшее	память	устойчива	заметка
вставками	`Θ(n²)`	`Θ(n²)`	`O(1)`	да	адаптивна: `Θ(n)` на почти упорядоченных
выбором	`Θ(n²)`	`Θ(n²)`	`O(1)`	нет	лишь `Θ(n)` обменов
пузырёк	`Θ(n²)`	`Θ(n²)`	`O(1)`	да	ранний выход на упорядоченном
Шелла	~`Θ(n^1.5)` для шагов Кнута, на практике	зависит от шагов	`O(1)`	нет	вставки с прыжками
слиянием	`Θ(n·log n)`	`Θ(n·log n)`	`Θ(n)`	да	гарантия + устойчивость
быстрая	`Θ(n·log n)`	`Θ(n²)`	`Θ(log n)`	нет	на месте, быстра на практике
пирамидальная	`Θ(n·log n)`	`Θ(n·log n)`	`O(1)`	нет	гарантия + на месте
подсчётом	`Θ(n + k)`	`Θ(n + k)`	`Θ(n + k)` (`Θ(k)`, если устойчивость не нужна)	да	целые в малом диапазоне
поразрядная	`Θ(d(n+b))`	`Θ(d(n+b))`	`Θ(n+b)`	да	целые/строки фикс. длины

Нижняя граница - водораздел

Сортировки СРАВНЕНИЯМИ упираются в Ω(n·log n) (дерево решений: n! листьев → высота log₂(n!) = Θ(n·log n)). Слияние и пирамидальная её достигают в худшем случае, быстрая - в среднем; в своём классе они оптимальны. Обойти границу можно, лишь НЕ сравнивая, а адресуясь по значению: подсчётом (Θ(n+k)) и поразрядно (Θ(d(n+b))) - но только для целых ключей подходящего вида.

Дерево выбора: какую сортировку под что

Что известно про данные/задачу	Бери
целые в малом диапазоне `k`	подсчётом (`Θ(n+k)`)
целые/строки фикс. длины, много данных	поразрядную (`Θ(d(n+b))`)
данные почти упорядочены	вставками / Timsort (`~Θ(n)`)
нужна устойчивость (многоключевая)	слияние / Timsort
дефицит памяти + гарантия `n·log n`	пирамидальную
крохотный массив (десятки)	вставками
всё прочее	встроенную (Timsort/introsort)

Три сквозные идеи

Адаптивность - цена падает с упорядоченностью входа (вставками, Timsort). Реальные данные часто почти упорядочены, поэтому это не мелочь.

Устойчивость - равные ключи сохраняют порядок; позволяет собирать многоключевую сортировку (от менее важного ключа к более важному устойчиво). Устойчивы вставками, слияние, подсчётом.

Гибриды в проме - Timsort (устойчивое адаптивное слияние для объектов) и introsort (быстрая + пирамидальная + вставки для чисел) собраны из изученных глав и закрывают слабости частей. По умолчанию бери встроенную.

Связи с остальным курсом

Рекуррентности (раздел 3) дали n·log n слияния и быстрой (2T(n/2)+n) и линейное построение кучи (Σ h/2ʰ).

Массивы (раздел 4) - основа: сортировки на месте, локальность памяти (почему быстрая обгоняет пирамидальную по константе), куча в массиве.

Поиск и порядковые статистики (следующий раздел) - разбиение быстрой сортировки лежит в основе быстрого выбора k-го элемента; двоичный поиск живёт на отсортированном массиве.

Хеш-таблицы (дальше) - за подсчётом и множеством стоит адресация по значению, идею которой раздел уже использовал.

Чек-лист: объясни своими словами

Почему сортировка вставками адаптивна и устойчива, а выбором - нет.
Что такое сортировка Шелла и почему её последний шаг - 1.
Почему слияние - n·log n в любом случае и чего это стоит по памяти.
Как работает разбиение Хоара и откуда у быстрой сортировки худший случай.
Почему построение кучи - Θ(n), а пирамидальная сортировка - n·log n на месте.
Как дерево решений доказывает границу Ω(n·log n).
Почему подсчёт и поразрядная обходят эту границу и чем за это платят.
Что такое устойчивость и как собрать сортировку по двум ключам.
Что такое Timsort и introsort и почему в библиотеках стоят гибриды.
Как выбрать сортировку под свойства данных.

Что дальше

Сортировки разобраны от простых до оптимальных и за предел сравнений; ты умеешь выбирать под данные. Дальше - поиск и порядковые статистики: двоичный поиск во всех его границах и выбор k-го элемента без полной сортировки (на разбиении из этой главы).