Информатика · объяснение и практика
Сортировка подсчётом: диапазон значений важнее числа разрядов
Сортировка подсчётом: частоты целых ключей, сдвиг отрицательного диапазона и отличие числа значений от ширины диапазона.

В теме Методы алгоритмов: углубление · Учебная карта
В маршруте Сортировки и сравнение строк · 10 тем
Главная мысль
Сортировка подсчётом использует небольшую таблицу возможных целых ключей. Сначала определяют частоты, затем места элементов. В обычной реализации затраты зависят не только от числа записей n, но и от ширины диапазона R: время и память таблицы требуют учитывать R.
Для какого набора подходит таблица частот
Если оценки лежат в небольшом известном диапазоне, каждому возможному значению можно выделить отдельную ячейку. Проход по входным данным увеличивает счётчик соответствующей ячейки. После этого известны все частоты, включая нулевые для значений, которые в данном наборе не встретились.
Небольшое количество различных значений ещё не гарантирует маленькую таблицу прямой адресации. Два числа, отличающиеся на миллиард, дают широкий диапазон, если выделять ячейку для каждого промежуточного целого. В таком случае нужна другая структура либо предварительное сжатие координат, которое тоже имеет собственную стоимость.
Сдвигаем отрицательные ключи
Для целых от минимума m до максимума M индекс можно вычислять как x−m. Тогда самый маленький ключ попадает в ячейку ноль, а самый большой — в последнюю. Ширина таблицы равна M−m+1. Само значение числа при этом не меняется: сдвиг относится только к адресу его счётчика.
Возьмём набор −3,−1,−3,0. Здесь минимум−3, максимум 0, поэтому нужны четыре ячейки. В них последовательно записаны частоты 2,0,1,1 для ключей−3,−2,−1,0. Чтобы получить отсортированные голые числа, можно выписать каждый ключ столько раз, сколько показывает его частота.
Пример
Вход: [−3,−1,−3,0]. Частоты для ключей [−3,−2,−1,0]: [2,0,1,1]. Итог: [−3,−3,−1,0].
Нулевая частота для−2 не означает пропущенную ячейку. Именно полный диапазон позволяет напрямую получить индекс как x+3.
Если вместе с ключом надо сохранить запись
Когда сортируются карточки с именами и оценками, простая выписка чисел потеряет имена. Тогда частоты превращают в накопленные границы мест, а сами исходные записи переносят в выходной массив. Направление обхода и обновление границы должны быть согласованы так, чтобы равные ключи сохранили исходный порядок.
В стандартном стабильном варианте с накопленными концами блоков вход обходят справа налево. Для каждого ключа сначала уменьшают его границу, затем помещают запись в освободившуюся позицию. Память выходного массива тоже учитывается. Метод полезен при подходящем диапазоне, но не становится универсально лучшим только потому, что не сравнивает ключи попарно.
От чтения к действию
А теперь — вы
Частые вопросы
Можно сортировать отрицательные целые?
Да. Адрес счётчика получают сдвигом x−min; число возможных адресов равно max−min+1.
Частоты достаточно для сортировки записей с именами?
Нет. Частоты сами по себе не сохраняют дополнительные поля исходных записей; нужен перенос записей в вычисленные позиции.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Поразрядная сортировка: зачем каждому проходу стабильность
LSD-сортировка по разрядам: проход от единиц к старшим цифрам, сохранение прежнего порядка и границы числовой модели.
Открыть темуСортировка вставками: как элемент находит место в готовом префиксе
Сортировка вставками на небольшом списке: готовый префикс, сдвиги больших элементов и сохранение порядка одинаковых значений.
Открыть тему