Radix Sort: Сортировка по разрядам

Цели урока

• Понять информационно-теоретический предел O(n log n) для сравнительных сортировок
• Освоить принцип поразрядной сортировки LSD
• Понять критическую роль стабильности в Radix Sort
• Реализовать Counting Sort как строительный блок
• Применять оптимизации: бóльшие основания, битовые операции

Предварительные знания

• Базовые алгоритмы сортировки (QuickSort, MergeSort)
• Понимание стабильности сортировки
• Базовые битовые операции

Radix Sort - одна из немногих сортировок, преодолевающих барьер O(n log n).

• Базы данных: сортировка целочисленных ключей
• GPU-вычисления: параллельная версия очень эффективна
• Сетевое оборудование: маршрутизация пакетов

Холлерит, перепись и сортировка перфокарт

Поразрядная сортировка старше самих компьютеров. В 1887 году Герман Холлерит, готовясь к переписи населения США 1890 года, изобрёл табуляционные машины на перфокартах. Его сортировальные машины раскладывали карты по корзинам, разряд за разрядом, что фактически и есть LSD radix sort, выполненный механически. Перепись 1880 года обрабатывали почти восемь лет, а с машинами Холлерита справились примерно за год. Компания Холлерита позже стала одной из основ IBM, а сортировка перфокарт по разрядам оставалась рабочим приёмом вплоть до эпохи электронных компьютеров.

Предел сравнительных сортировок

Все известные нам сортировки - QuickSort, MergeSort, HeapSort - работают через **сравнения** элементов. И у всех есть общий потолок: **O(n log n)**. Это не недостаток реализации - это **математический предел**.

Почему? Каждое сравнение даёт 1 бит информации (больше/меньше). Чтобы упорядочить n элементов, нужно отличить n! перестановок. Информационная ёмкость: log₂(n!) ≈ n log n бит. Быстрее не получить через сравнения.

Но что если не сравнивать элементы между собой? Что если использовать СТРУКТУРУ данных - например, то что числа состоят из цифр?

**Метафора: почтовое отделение**

Представь, что ты работаешь на почте и нужно отсортировать 10,000 писем по почтовому индексу (6 цифр). Можно сравнивать попарно - это O(n log n) ≈ 130,000 сравнений. Но почтовики делают умнее!

Это и есть **Radix Sort** - сортировка, которая смотрит не на отношение элементов друг к другу, а на их **внутреннюю структуру** (цифры). И она может работать быстрее O(n log n)!

Идея Radix Sort: от младшего разряда к старшему

Radix Sort работает так: мы сортируем числа **по одной цифре за раз**, начиная с **младшего разряда** (единиц). Это называется **LSD Radix Sort** (Least Significant Digit first).

Кажется нелогичным - почему начинать с конца? Ведь сотни важнее единиц! Но именно в этом гениальность алгоритма.

Смотри, что произошло: после каждого прохода числа отсортированы по **всем обработанным разрядам вместе**. После прохода 1 - по единицам. После прохода 2 - по двум последним цифрам (как двузначные числа). После прохода 3 - полностью!

Ключ к пониманию: мы не просто сортируем по текущему разряду - мы СОХРАНЯЕМ порядок из предыдущих проходов для одинаковых цифр.

Почему стабильность - это всё

Корректность Radix Sort держится на одном свойстве: **стабильности** сортировки на каждом шаге. Если сортировка нестабильна - алгоритм даёт неправильный результат!

**Что такое стабильность?** Стабильная сортировка сохраняет относительный порядок элементов с одинаковыми ключами. Если A и B имеют одинаковое значение, и A был раньше B - после сортировки A останется раньше B.

Контрпример нестабильной сортировки: [12, 21]. По единицам: [21, 12]. По десяткам: ящик 1 [12], ящик 2 [21] → [12, 21]. Вроде верно. Но [121, 211, 112, 212]: после нестабильной сортировки порядок сломается!

Итак, для Radix Sort нам нужна стабильная сортировка по одной цифре. Самый простой и эффективный выбор - **Counting Sort**.

Counting Sort: стабильная O(n+k) сортировка

**Counting Sort** - идеальный строительный блок для Radix Sort. Она стабильна, работает за O(n+k), и идеально подходит для маленького диапазона значений (как цифры 0-9).

**Идея Counting Sort** проста: вместо сравнений - подсчёт. Сначала считаем, сколько раз встречается каждое значение, потом вычисляем позиции.

Проход справа налево критичен: если элемент X стоит в массиве позже элемента Y (оба с одной цифрой), X попадёт на более правую позицию в output. Порядок сохранён!

Полный код Counting Sort для одного разряда:

LSD Radix Sort: полная реализация

Теперь у нас есть все кирпичики. LSD Radix Sort просто применяет Counting Sort к каждому разряду, от младшего к старшему.

**Анализ сложности:**

Radix Sort побеждает когда d < log n, то есть когда числа 'короткие' относительно их количества. Для 32-битных int: d ≤ 10, а log₂(n) > 10 при n > 1024.

**Пошаговая трассировка:**

Оптимизации и варианты

Базовый Radix Sort с основанием 10 можно значительно ускорить, используя бóльшие основания.

**Идея: основание 256 (байты)**

>>> (беззнаковый сдвиг) важен для правильной работы с отрицательными числами в JavaScript/TypeScript.

**Обработка отрицательных чисел**

**MSD Radix Sort - альтернативный подход**

**Когда Radix Sort лучше QuickSort:**

Итоги

• Radix Sort сортирует числа по разрядам от младшего к старшему (LSD)
• На каждом шаге используется стабильная Counting Sort - без стабильности алгоритм не работает
• Сложность O(d × n), где d - количество разрядов
• С основанием 256 (байты) для 32-битных чисел нужно всего 4 прохода
• Radix Sort быстрее O(n log n) сортировок когда d < log n

Связи с другими алгоритмами

Radix Sort использует Counting Sort и связан с Bucket Sort

• Counting Sort — Строительный блок для одного разряда
• Bucket Sort — Похожая идея распределения по корзинам
• Insertion Sort — Комбинируется для малых групп

Связанные уроки

• alg-08-counting-sort — Counting Sort - стабильный строительный блок каждого прохода Radix Sort, без него алгоритм не работает
• alg-05-merge-sort — Merge Sort O(n log n) для любых данных, Radix Sort O(d*n) быстрее когда d < log n - разные применимости
• alg-06-quick-sort — Quick Sort in-place O(log n) памяти, Radix Sort требует O(n) - Memory vs Speed trade-off
• ds-06-hash-intro — LSD Radix Sort и хеш-таблица используют схожую идею: разбиение по корзинам на основе части ключа
• alg-25-rabin-karp — Suffix Array строится эффективно с помощью Radix Sort по суффиксам - O(n log n) вместо O(n log^2 n)
• arch-01-binary