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

Описание алгоритма

Если количество возможных различных элементов в множестве относительно невелико, то сортировка подсчетом является одним из самых оптимальных решений.

Главная идея алгоритма: посчитать количество элементов каждого типа, а затем выставить нужное количество элементов первого по порядку типа, затем второго и так далее.

Например, если даны натуральные числа от $1$ до $100$. Создадим массив размера $100$, в котором будем хранить на $i$-ом месте, сколько раз число $i$ встретилось в этом массиве. Пройдемся по всем числам, и увеличим соответствующее значение массива на $1$. Таким образом мы подсчитали, сколько раз какое число встретилось. Теперь можно просто пройтись по этому массиву и вывести $1$ столько раз, сколько раз встретилась $1$, вывести $2$ столько раз, сколько встретилась $2$, и так далее.

Красивая реализация (Вкладка COU).

Асимптотика

Время работы такого алгоритма составляет $O(U + N)$, где $U$ - число возможных значений, $N$ - число элементов в массиве.

Вариант реализации

Сначала посчитаем, сколько элементов каждого типа встретилось. Пусть результат лежит в массиве $cnt$. Затем определим, где в итоговом массиве должны начинаться элементы $1$-го типа, $2$-го и так далее. Для этого посчитаем префиксные суммы. Пусть все элементы лежат в диапазоне от $1$ до $C$. Тогда $pref[i] = cnt[1] + cnt[2]+ \dots + cnt[i]$. Если теперь пройтись от $1$ до $C$ по массиву $pref$, то все числа в нем будут идти в порядке невозрастания. Более того, элемент, равный $x$, будет лежать в отсортированном массиве на позициях $[pref[x - 1], pref[x])$ (нумерация с нуля).

Расставим элементы на места: сделаем еще один проход по исходному массиву, поддерживая инвариант: $pref[i]$ - позиция следующего элемента типа $i$. После обработки очередного элемента счетчик для соответствующего типа уменьшается на $1$.

for i=0...n-1:
    cnt[a[i]]++
pref[0] = 0
for i = 1..C:
   pref[i] = pref[i - 1] + cnt[i]
for i=0...n-1:
    res[pref[a[i]] - 1] = a[i]
    pref[a[i]]--

Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko