Counting Sort

Проблема

Теоретический предел любой сортировки, основанной на попарных сравнениях, - O(n log n): это доказывается через дерево решений. Но если заранее известно, что значения - это целые числа из небольшого диапазона (например, оценки от 0 до 100 или возраст людей), сравнивать их вообще не обязательно - можно посчитать, сколько раз встречается каждое значение.

Решение

Алгоритм заводит вспомогательный массив count длиной в диапазон возможных значений и проходит по входному массиву, увеличивая count[значение] для каждого элемента. Затем count превращается в массив префиксных сумм - count[v] теперь означает «сколько элементов ≤ v», то есть последнюю позицию значения v в отсортированном массиве. После этого исходный массив проходится справа налево: каждый элемент кладётся в выходной массив на позицию count[значение] - 1, а счётчик уменьшается - обход справа налево нужен именно для устойчивости сортировки.

Как это работает

Возьмём массив [4, 2, 2, 8, 3, 3, 1] (n = 7). Значения лежат в диапазоне 1-8, значит k = 8. Сравнивающая сортировка на 50 элементах сделала бы порядка n·log₂n ≈ 50 · 5.64 ≈ 282 сравнений, а сортировка подсчётом на этом же n при k = 101 (например, оценки 0-100) выполняет всего n + k = 151 «элементарных» операций - меньше и без единого сравнения.

Для [4, 2, 2, 8, 3, 3, 1] подсчёт вхождений (индекс = значение - 1, так как min = 1) даёт count = [1, 2, 2, 1, 0, 0, 0, 1] - единица встретилась 1 раз, двойка 2 раза, тройка 2 раза, четвёрка 1 раз, восьмёрка 1 раз. После построения префиксных сумм получается [1, 3, 5, 6, 6, 6, 6, 7] - последнее значение массива, 7, равно длине входа, что и должно быть: все 7 элементов ≤ максимума.

Устойчивость проверяется на дубликатах с меткой: пусть на позициях 0 и 2 исходного массива стоят два одинаковых значения A и C ([A(2), B(5), C(2)]). Обход справа налево берёт C первым - он получает индекс count[0] - 1 = 1, - затем A получает освободившийся индекс 0. Итог `[A, C, B]` - относительный порядок A перед C сохранён, хотя C был обработан раньше физически.

Крайний случай в другую сторону: сортировка n = 1000 случайных 32-битных целых чисел. Диапазон k достигает 2^32 ≈ 4.3 миллиарда - массив count такого размера физически невозможно выделить в памяти обычного компьютера. Здесь алгоритм ломается не по логике, а по ресурсам: O(n + k) перестаёт быть практичным, когда k на порядки больше n.

Именно эта проблема решается поразрядной сортировкой (radix sort): вместо одного прохода по всему диапазону значений она сортирует по разрядам числа, каждый раз вызывая устойчивую сортировку подсчётом с k = 10 (для десятичных разрядов). На примере [170, 45, 75, 90, 802, 24, 2, 66] после прохода по разряду единиц получается [170, 90, 802, 2, 24, 45, 75, 66], после разряда десятков - [802, 2, 24, 45, 66, 170, 75, 90], а после разряда сотен массив уже полностью отсортирован: [2, 24, 45, 66, 75, 90, 170, 802].

Каждый такой проход обязан быть устойчивым - иначе более старший разряд перепутает порядок, уже установленный младшими разрядами. Это единственная причина, по которой counting sort вообще заботится об устойчивости: сама по себе задача «отсортировать целые числа» её не требует, но её реализация как строительного блока radix sort требует обязательно.

Первое известное описание идеи принадлежит Гарольду Сьюарду (Harold H. Seward) в его магистерской диссертации 1954 года в MIT - там же встречается и ранняя формулировка радикс-сортировки, использующей тот же принцип подсчёта по разрядам.

Итог: сортировка подсчётом - это не «более быстрая» сортировка сравнениями, а алгоритм из другого класса, который обменивает время (пропуск сравнений) на пространство (массив count размером k). Пока k сопоставим с n, обмен выгоден; как только k начинает расти отдельно от n, выгоднее либо radix sort (разбить один большой диапазон на несколько маленьких), либо bucket sort (для непрерывных, а не дискретных значений).

Нюансы выбора

Вместо radix sort, когда диапазон сам по себе мал - если k уже порядка десятков-сотен (оценки, возраст, ранги), не нужно городить поразрядную обработку, один проход counting sort проще и не медленнее.

Как внутренний шаг radix sort, когда диапазон одного разряда фиксирован (0-9 для десятичных чисел, 0-255 для байтов) - здесь устойчивость обязательна, не опциональна.

Против bucket sort - когда данные дискретны, а не непрерывны: у counting sort ключи - это сами индексы ячеек, у bucket sort - диапазоны значений внутри корзины, которые всё равно надо досортировать. Для целых чисел известного диапазона counting sort и проще, и точнее.

Не выбирать при неизвестном заранее диапазоне - если min/max нельзя оценить до запуска (поток данных без ограничений), нет гарантии, что k останется разумным; здесь безопаснее сравнивающая сортировка с предсказуемой O(n log n) памятью и временем.

Для построения гистограмм наряду с сортировкой - если всё равно нужно посчитать частоту каждого значения (аналитика, статистика), массив count уже содержит этот результат бесплатно, до всякой сортировки.

Примеры в коде

Магистерская диссертация Гарольда Сьюарда (MIT, 1954) - первое зафиксированное описание идеи подсчёта вхождений для сортировки и связанной с ней поразрядной сортировки.

Построение суффиксных массивов (алгоритм DC3/skew) - внутренние проходы поразрядной сортировки троек символов реализуются именно устойчивой сортировкой подсчётом, критичной для итогового O(n) времени построения.

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

Конкурентное программирование - задача "counting sort" часто маскируется под "отсортируй массив с элементами от 1 до 10^5" или "посчитай инверсии в ограниченном диапазоне", где решение в лоб через сравнения проходит по времени, но подсчёт вхождений быстрее и проще.

Когда применять

• Когда сортируемые значения - целые числа из заранее известного и не слишком большого диапазона (оценки, возраст, ранги).
• Как строительный блок для radix sort - сортировка подсчётом по одному разряду это его внутренний шаг.

Примеры из практики

• Radix sort использует сортировку подсчётом как подпрограмму для упорядочивания чисел по каждому разряду.
• Обработка изображений - построение гистограммы яркости пикселей (значения 0-255) и сортировка пикселей по яркости используют по сути тот же принцип подсчёта.