Конспект: нижняя граница и сортировки без сравнений

Понятия

Нижняя граница сравнений - любая сортировка, узнающая о данных только через сравнения, в худшем случае делает Ω(n·log n) сравнений. Доказано, а не «пока не придумали».

Дерево решений - модель сортировки сравнениями: узел - сравнение (развилка да/нет), лист - выданная перестановка. Листьев ≥ n!, высота ≥ log₂(n!) = Θ(n·log n); высота - число сравнений в худшем случае.

Сортировка подсчётом - для целых из диапазона [0, k): массив счётчиков размера k, один проход считает вхождения, второй выписывает значения по порядку. Θ(n + k), без сравнений. Устойчивый вариант - через префиксные суммы.

Поразрядная сортировка (LSD) - устойчивый подсчёт по одной цифре за раз, от МЛАДШЕЙ к старшей; после d проходов массив отсортирован. Θ(d·(n + b)), b - основание.

Что унести

Нижняя граница n·log n - только для СРАВНЕНИЙ. Доказательство: n! возможных порядков → n! листьев → высота log₂(n!) = Θ(n·log n). log₂(n!) = Θ(n·log n), потому что n! ≤ n^n (сверху) и n! ≥ (n/2)^(n/2) (снизу). Отсюда слияние, быстрая и пирамидальная - оптимальны в классе сравнений.

Кто НЕ сравнивает, а адресуется по значению, границу обходит:

Подсчёт хорош при k ≈ n (тогда Θ(n)); при огромном k счётчики раздуваются. Поразрядная снимает это ограничение - d дешёвых проходов с маленьким b вместо одного огромного k; линейна при небольшом фиксированном d.

Блочная - корзина ⌊x·n⌋, вставки внутри, склейка. Линия только в среднем по данным: пара в одной корзине с вероятностью 1/n, инверсий (n−1)/4. Скученные данные дают почти квадрат.

Устойчивость - сердце поразрядной: проход по старшей цифре не должен рушить порядок, наведённый младшими. И направление обязательно от МЛАДШЕЙ к старшей.

Главная мысль: выбор сортировки начинается с вопроса «что я знаю про ключи?». Целые в узком диапазоне - подсчёт (Θ(n)); целые фиксированной ширины - поразрядная (Θ(n)); произвольные сравнимые - n·log n-сортировка.

Ловушки джокера

Ищешь сортировку сравнениями быстрее n·log n. Её нет - доказано. Улучшай константу или обходи через не-сравнения.

Считаешь n·log n пределом для ЛЮБОЙ сортировки. Нет - только для сравнений; подсчёт и поразрядная линейны.

Применяешь подсчёт к огромному диапазону k. Θ(n + k) вырождается в Θ(k) - память и время съедены.

Берёшь неустойчивую сортировку в поразрядной. Каждый проход перемешивает предыдущий - результат неверен.

Идёшь в поразрядной от старшей цифры (LSD). Младшие проходы разрушают старший порядок.

Взял блочную сортировку для данных с длинным хвостом. Числа сгрудятся в нескольких корзинах, и линия станет квадратом: равномерность - условие, а не украшение.

Проверь себя

Как дерево решений доказывает границу Ω(n·log n)?

Почему log₂(n!) = Θ(n·log n)?

Почему сортировка подсчётом не противоречит нижней границе?

Сколько стоит подсчёт и когда он применим?

Почему поразрядной нужны устойчивость и направление «от младшей цифры»?

Почему блочная сортировка линейна только в среднем и только на равномерных данных?