Сортировка подсчётом
Сортировка подсчётом вообще не сравнивает значения. Если вы знаете, что каждое значение — целое число, скажем, от 1 до 40, можно просто посчитать, сколько раз встречается каждое, и по этим количествам вычислить, где место каждого. Для малого диапазона это едва ли не самая быстрая сортировка.
Подсчёт
Найдите наименьшее и наибольшее значения и заведите по счётчику на каждое значение между ними, все с нуля. Прочитайте список один раз от начала до конца и прибавляйте единицу к счётчику каждого встреченного значения. Теперь счётчики образуют гистограмму: сколько единиц, сколько двоек и так далее. При n значениях и k счётчиках это занимает n шагов.
Сложение
Значения, равные наименьшему, идут первыми, поэтому их блок начинается с места 1. Блок следующего значения начинается сразу после них, и так далее: каждый блок начинается после суммы всех предыдущих количеств. Эти нарастающие итоги, называемые префиксными суммами, превращают гистограмму в карту отсортированного списка. Это занимает k шагов.
Размещение
Прочитайте список второй раз и переместите каждое значение на следующее свободное место его блока. Поскольку значения перемещаются в том порядке, в котором встречаются, равные значения сохраняют исходный порядок: сортировка подсчётом устойчива. Скопируйте буфер обратно, и список отсортирован. Приложение показывает, как каждый счётчик снова уменьшается по мере размещения его значений.
Пример
Возьмём 4, 1, 3, 4, 2, 1, 4. Счётчики для значений от 1 до 4 в итоге равны 2, 1, 1 и 3. Сложение даёт блоки: единицы на местах 1 и 2, двойка на месте 3, тройка на месте 4, а четвёрки на местах с 5 по 7. Размещение значений в порядке списка даёт 1, 1, 2, 3, 4, 4, 4: подсчитано 7 значений, 14 перемещений, 4 счётчика, ни одного сравнения.
Когда её применять
Общая работа растёт как n + k. Когда k мало по сравнению с n, например тысяча баллов за экзамен от 0 до 100, сортировка подсчётом быстрее любой сортировки сравнениями, которой нужно около n log₂ n сравнений. При широком диапазоне она расточительна: нескольким значениям, разбросанным до миллиона, нужен миллион счётчиков. Поразрядная сортировка решает эту проблему, запуская сортировку подсчётом по разу на каждую цифру, так что каждому проходу нужно всего десять счётчиков. Harold Seward описал сортировку подсчётом вместе с поразрядной сортировкой в 1954 году.
Попробуйте сами
Откройте приложение и нажмите «Шаг». Полоса между списком и строкой буфера показывает по одному счётчику на значение. Смотрите, как счётчики заполняются при чтении списка, блоки появляются в буфере, когда количества складываются, а счётчики снова уменьшаются по мере размещения значений. Выберите мало разных значений, чтобы увидеть большие блоки, или введите далеко отстоящие числа, чтобы увидеть, сколько счётчиков нужно широкому диапазону.
Часто задаваемые вопросы
Какова временная сложность сортировки подсчётом?
O(n + k) для n значений и k возможных значений и O(n + k) дополнительной памяти для счётчиков и буфера.
Почему сортировка подсчётом не всегда самая быстрая?
Потому что её стоимость зависит от диапазона значений, а не только от их количества. Если диапазон намного больше списка, большинство счётчиков остаются на нуле, а время и память тратятся впустую.
Может ли сортировка подсчётом работать с отрицательными числами?
Да. Счётчики идут от наименьшего значения до наибольшего, поэтому вычтите наименьшее значение, чтобы получить индекс счётчика. Приложение делает так же.
Устойчива ли сортировка подсчётом?
Да, если значения перемещаются в порядке списка на следующее свободное место своего блока. На этом основана поразрядная сортировка.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать сортировку подсчётом