Сортировка подсчётом¶

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

¶История

Идея сортировки подсчётом впервые была описана в 1954 году американским математиком Гарольдом Сьюардом в его докторской диссертации, посвящённой методам сортировки данных на магнитных лентах. В 1960-х годах алгоритм получил распространение в связи с развитием компьютерной обработки данных, где требовалась быстрая сортировка целых чисел или ключей с ограниченным диапазоном. В советской научной литературе метод упоминается в работах по программированию и вычислительной математике, начиная с 1970-х годов.

¶Принцип работы

Сортировка подсчётом выполняется в несколько этапов:

1. Определение диапазона значений. Находится минимальное (min) и максимальное (max) значение во входном массиве. Диапазон k = max - min + 1 определяет размер вспомогательного массива-счётчика.
2. Подсчёт частот. Создаётся массив count размером k, все элементы инициализируются нулями. Затем для каждого элемента входного массива вычисляется индекс index = элемент - min и значение count[index] увеличивается на 1.
3. Преобразование счётчика в массив позиций (кумулятивная сумма). Для каждого индекса i от 1 до k-1 выполняется count[i] = count[i] + count[i-1]. После этого count[i] содержит количество элементов, которые меньше или равны значению min + i.
4. Построение отсортированного массива. Создаётся выходной массив output того же размера, что и входной. Входной массив проходится в обратном порядке (для обеспечения устойчивости). Для каждого элемента x вычисляется индекс index = x - min, значение count[index] уменьшается на 1, и элемент помещается в output[count[index]].
5. Копирование результата. Отсортированный массив output копируется обратно во входной массив (или используется как результат).

¶Пример

Пусть входной массив: [4, 2, 2, 8, 3, 3, 1]. Диапазон значений: от 1 до 8, k = 8.

1. Массив счётчика после подсчёта: [1, 2, 2, 1, 0, 0, 0, 1] (индексы 0–7 соответствуют значениям 1–8).
2. После кумулятивной суммы: [1, 3, 5, 6, 6, 6, 6, 7].
3. Обратный проход:

• Элемент 1 (последний): count[0] = 1 → помещается в output[0], count[0] = 0.
• Элемент 3: count[2] = 5 → output[4], count[2] = 4.
• Элемент 3: count[2] = 4 → output[3], count[2] = 3.
• Элемент 8: count[7] = 7 → output[6], count[7] = 6.
• Элемент 2: count[1] = 3 → output[2], count[1] = 2.
• Элемент 2: count[1] = 2 → output[1], count[1] = 1.
• Элемент 4: count[3] = 6 → output[5], count[3] = 5.

1. Результат: [1, 2, 2, 3, 3, 4, 8].

¶Характеристики

¶Временная сложность

• Лучший случай: O(n + k), где n — количество элементов, k — диапазон значений.
• Средний случай: O(n + k).
• Худший случай: O(n + k).

¶Пространственная сложность

• O(n + k) — требуется дополнительная память для массива счётчика и выходного массива. При сортировке на месте (in-place) реализация невозможна без потери устойчивости или значительного усложнения.

¶Устойчивость

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

¶Ограничения

• Алгоритм применим только для данных, которые можно преобразовать в целые числа (или ключи с дискретными значениями). Для строк или чисел с плавающей точкой требуется предварительное отображение на целочисленный диапазон.
• Требует знания диапазона значений заранее или его вычисления за O(n). Если диапазон k значительно больше n, эффективность падает (например, при k = 10⁶ и n = 10³).
• Не подходит для сортировки данных с неизвестным или бесконечным диапазоном (например, произвольные вещественные числа).

¶Разновидности

¶Сортировка подсчётом с отрицательными числами

Стандартная реализация корректно обрабатывает отрицательные значения, если сдвиг min учитывается. Например, для массива [-5, 0, -3, 2] минимальное значение равно -5, диапазон k = 2 - (-5) + 1 = 8. Индекс для элемента -5: -5 - (-5) = 0, для 0: 0 - (-5) = 5.

¶Сортировка подсчётом для объектов

Если сортируются не сами числа, а объекты с ключами, алгоритм применяется к ключам, а объекты переставляются в соответствии с позициями ключей. Это требует дополнительного массива для хранения объектов или использования индексов.

¶Сортировка подсчётом с плавающей точкой

Для сортировки чисел с плавающей точкой с ограниченной точностью можно преобразовать их в целые числа путём умножения на степень десяти (например, для двух знаков после запятой: 3.14 → 314). Однако это увеличивает диапазон и может привести к потере точности.

¶Применение

Сортировка подсчётом широко используется в следующих областях:

• Обработка данных с ограниченным диапазоном: сортировка оценок (0–100), возрастов (0–120), кодов символов (0–255 для ASCII, 0–65535 для Unicode).
• Поразрядная сортировка (radix sort): сортировка подсчётом применяется как устойчивая подпрограмма для сортировки по отдельным разрядам чисел.
• Графические алгоритмы: сортировка пикселей по цвету или интенсивности (0–255 для каждого канала RGB).
• Базы данных: сортировка записей по ключам с небольшим числом уникальных значений (например, статусы заказов: «новый», «в обработке», «отправлен», «доставлен»).
• Статистика и анализ данных: построение гистограмм распределения частот, где сортировка подсчётом фактически является промежуточным этапом.

¶Сравнение с другими алгоритмами

Сортировка подсчётом выигрывает по скорости у всех сравнительных сортировок при малом диапазоне k, но проигрывает по памяти и универсальности.

¶Интересные факты

• Сортировка подсчётом является частным случаем более общего класса алгоритмов — сортировок распределением (distribution sort).
• В некоторых реализациях массив счётчика может быть заменён хеш-таблицей, если диапазон значений велик, но количество уникальных значений невелико. Однако это снижает устойчивость и увеличивает сложность до O(n log n) в худшем случае.
• Алгоритм лежит в основе метода «голубиной сортировки» (pigeonhole sort), где каждый элемент помещается в «ячейку» (голубиное гнездо) по значению ключа.
• В советской литературе сортировка подсчётом иногда называлась «сортировкой методом подсчёта» или «распределяющей сортировкой».

¶Критика

Основной недостаток сортировки подсчётом — зависимость от диапазона значений. При большом разбросе данных (например, сортировка миллионов чисел от 0 до 10⁹) алгоритм становится неэффективным из-за огромного расхода памяти. В таких случаях предпочтительнее использовать поразрядную сортировку, которая разбивает диапазон на разряды, или гибридные алгоритмы (например, introsort). Также алгоритм не подходит для сортировки данных, которые нельзя однозначно сопоставить целым числам без потери информации.

¶Источники

• Сьюард Г. «A method of sorting data on magnetic tape» (1954).
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (3-е издание, 2013).
• Кнут Д. «Искусство программирования. Том 3. Сортировка и поиск» (2-е издание, 1998).
• Вирт Н. «Алгоритмы и структуры данных» (1985).