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

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

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

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

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

Асимптотика

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

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

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

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

---

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

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