Counting Sort: O(n) без сравнений

Цели урока

• Понять нижнюю границу O(n log n) для comparison sorts
• Реализовать Counting Sort (стабильную версию)
• Понять Radix Sort и когда его использовать
• Знать Bucket Sort и его ограничения

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

• O(n²) сортировки
• Big O

• O(n²) сортировки

O(n log n) - это предел для сортировок сравнениями. Но если мы знаем что-то о данных, можем сортировать за O(n)! Counting, Radix, Bucket - три способа обойти теоретический предел.

• Сортировка по возрасту (0-150) - Counting Sort
• Сортировка телефонных номеров - Radix Sort
• Сортировка координат (uniform distribution) - Bucket Sort
• Базы данных - индексы по числовым полям

Гарольд Сьюард и сортировка подсчётом в MIT

Сортировку подсчётом описал Гарольд Сьюард в 1954 году в своей магистерской работе в MIT, в Lincoln Laboratory. В той же работе он впервые сформулировал и поразрядную сортировку (radix sort) в виде, пригодном для цифровых машин. Это было время, когда память измерялась тысячами слов, а сортировка данных была одной из главных задач первых компьютеров. Идея Сьюарда выглядела почти еретически на фоне сортировок сравнением: не сравнивать элементы вообще, а просто посчитать, сколько раз встречается каждое значение, и собрать результат из счётчиков. Для целых чисел в узком диапазоне это давало линейное время, обходя предел O(n log n). Позже Дональд Кнут разобрал и подсчёт, и radix в третьем томе The Art of Computer Programming (Sorting and Searching, 1973), закрепив за ними место в каноне. Distribution counting, как Кнут называл метод, стал фундаментом для radix sort, который десятилетиями использовали для сортировки перфокарт на электромеханических табуляторах ещё до электронных компьютеров.

Предел сортировок сравнениями

**Теорема:** любая сортировка, основанная на сравнениях, не может быть быстрее O(n log n) в худшем случае.

**log(n!) = Θ(n log n)** по формуле Стирлинга. Это теоретический предел для comparison-based сортировок.

**Но!** Если мы знаем что-то о данных (диапазон значений, тип), можно сортировать быстрее, НЕ сравнивая элементы.

Идея Counting Sort

**Counting Sort** подходит когда элементы - целые числа в известном диапазоне [0, k].

1. Подсчитать сколько раз встречается каждое значение
2. Вычислить позиции через prefix sum
3. Разместить элементы на правильные позиции

Реализация Counting Sort

**Упрощённая версия** (не стабильная, но проще понять):

**Стабильность важна** для Radix Sort! Без неё Radix Sort не работает корректно.

Когда использовать Counting Sort

**Когда использовать:**

• k = O(n) - диапазон сравним с количеством элементов
• Элементы - неотрицательные целые (или можно сдвинуть)
• Нужна стабильность
• Память не критична

**Когда НЕ использовать:**

• k >> n - например, сортировка 100 чисел в диапазоне 0..10⁹
• Элементы - float, строки, объекты
• Память ограничена

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

**Radix Sort** - сортируем по разрядам (цифрам), от младшего к старшему (LSD) или наоборот (MSD).

**Сложность Radix Sort:** O(d × (n + k)) где d = количество разрядов, k = основание (обычно 10 или 256). При d = O(log n) получаем O(n log n), но константы лучше.

Bucket Sort: распределение по корзинам

**Bucket Sort** - распределяем элементы по "корзинам", сортируем корзины, объединяем.

**Ожидаемое время O(n)** если элементы равномерно распределены. При плохом распределении - O(n²) (все в одной корзине).

Non-comparison сортировки

• Comparison sorts: нижняя граница O(n log n)
• Counting Sort: O(n+k), для целых 0..k
• Radix Sort: O(d(n+k)), сортировка по разрядам
• Bucket Sort: O(n) avg, для равномерного распределения
• Все требуют знание о данных
• Trade-off: время vs память vs универсальность

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

Non-comparison сортировки часто используются как подпрограммы в других алгоритмах.

• Suffix Array — Radix Sort для построения
• Хеш-таблицы — Bucket sort использует похожую идею

Вопросы для размышления

• При каких условиях counting sort становится практически непригодным, несмотря на O(n) сложность?
• Как counting sort используется как суб-процедура в radix sort?
• Какие задачи в обработке данных выигрывают от того, что диапазон значений заранее известен?

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

• alg-05-merge-sort — Merge Sort O(n log n) и универсален, Counting Sort O(n+k) но требует целых чисел в известном диапазоне - разные trade-off
• alg-38-radix-sort — Counting Sort - строительный блок Radix Sort: стабильный проход по одному разряду
• ds-06-hash-intro — Bucket Sort использует ту же идею распределения по слотам, что и хеш-таблица: элемент попадает в корзину по своему значению
• alg-01-big-o — Нижняя граница O(n log n) для comparison sorts доказывается через decision tree - хороший пример применения Big O для доказательства невозможного
• alg-04-basic-sorts — O(n^2) сортировки универсальны и in-place, Counting Sort быстрее но только для специфических данных
• prob-02-combinatorics