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

Сортировка подсчётом (counting sort) считает, сколько раз встречается каждое значение, и по этим счётчикам выстраивает результат. Работает за $O(N+K)$, где значения — целые числа от $0$ до $K$.

Зачем нужно

Любая сортировка сравнением не быстрее $\Omega (N\log N)$ (см. Сортировка). Если значения — небольшие целые числа, можно вообще не сравнивать: использовать значение как индекс. Тогда сортировка идёт за линейное время.

Как работает

Простая версия

count = [0 ... 0]               // K + 1
for i = 0 ... N
    count[arr[i]]++
for i = 0 ... K
    while count[i] > 0
        print(i)
        count[i]--

$T(N)=O(N+K)$: первый цикл — $N$ шагов, во втором $K+1$ значений и всего $N$ печатей. Она печатает значения, а не переставляет элементы. Для чисел этого достаточно, для записей по ключу — нет: на лекции эта версия названа неустойчивой.

Устойчивая версия

count = [0 ... 0]               // K + 1
result = [ ... ]                // N
for i = 0 ... N
    count[arr[i]]++
for i = 1 ... K
    count[i] += count[i − 1]
for j = N − 1 ... 0
    result[count[arr[j]] − 1] = arr[j]
    count[arr[j]]--

После префиксных сумм count[v] — число элементов $\le v$: значения $v$ занимают в результате позиции [count[v−1], count[v]). Проход с конца кладёт самый правый из равных на последнее место блока, следующий — левее. Порядок равных сохраняется — сортировка устойчива. Пример: счётчики 5 7 9 1 5 → префиксные суммы 5 12 21 22 27.

На доске

В последнем цикле записано = arr[i] вместо = arr[j], префиксные суммы — 5 13 22 23 28 (ошибка в $5+7$), а оценка — $T=O(N)$, $M=O(N)$. Честно $O(N+K)$ и по времени, и по памяти. См. конспект.

Тонкости

• $K$ должно быть маленьким. При $K\gg N$ время и память определяет $K$: десять чисел до $10^9$ — миллиард счётчиков.
• Значения должны быть целыми неотрицательными. Отрицательные сдвигают на минимум, дробные и строки так не отсортировать.
• Нижней оценке $\Omega (N\log N)$ сортировка подсчётом не противоречит: теорема говорит только о сортировках сравнением.

Не из лекции

• Сдвиг на минимум: count[arr[i] − min]++, тогда $K=\max -\min$.
• Устойчивость нужна, когда подсчёт — шаг более сложной сортировки: поразрядная сортировка сортирует числа по одной цифре за проход и опирается на то, что порядок по младшим цифрам не сломается.

Частые ошибки

• Применять при огромном диапазоне значений.
• Идти в устойчивой версии с начала массива — порядок равных разворачивается.
• Забыть − 1 в result[count[arr[j]] − 1]: count[v] указывает за последнее место блока.
• Считать оценку $O(N)$, забыв про $K$.