Сортировка подсчетом
Описание алгоритма
Если количество возможных различных элементов в множестве относительно невелико, то сортировка подсчетом является одним из самых оптимальных решений.
Главная идея алгоритма: посчитать количество элементов каждого типа, а затем выставить нужное количество элементов первого по порядку типа, затем второго и так далее.
Например, если даны натуральные числа от $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]]--
Немного о стабильности
Можно заметить, что в таком виде сортировка подсчетом не является стабильной. То есть относительный порядок элементов, которые мы считаем равными, не сохраняется (более того, порядок меняется на обратный). Рассмотрим на примере:
Пусть нам задан массив пар [{1, 'a'}, {3, 'b'}, {1, 'c'}]
, который мы хотим отсортировать по возрастанию первого элемента (числа) в паре. Массив $cnt$ будет иметь вид [0, 2, 0, 1]
, а массив $pref$ - [0, 2, 2, 3]
. Посмотрим, что будет происходить с каждой итерацией последнего цикла.
- $i = 0,\ pref[a[i].first] - 1 = 1 \Longrightarrow res = \text{[null, \{1, 'a'\}, null]},\ pref = [0, 1, 2, 3]$
- $i = 1,\ pref[a[i].first] - 1 = 2 \Longrightarrow res = \text{[null, \{1, 'a'\}, \{3, 'b'\}]},\ pref = [0, 1, 2, 2]$
- $i = 2,\ pref[a[i].first] - 1 = 0 \Longrightarrow res = \text{[\{1, 'c'\}, \{1, 'a'\}, \{3, 'b'\}]},\ pref = [0, 0, 2, 2]$
Элементы {1, 'a'}
и {1, 'c'}
теперь идут в обратном порядке. Почему так происходит? Когда мы обрабатываем элемент $i$, мы уменьшаем значение в $pref[a[i]]$ на единицу, то есть, когда мы встретим еще один элемент (например с индексом $j > i$) с таким же значением, для него $pref[a[j]]$ окажется меньше, и сам элемент $a[j]$ займет позицию с меньшим индексом в отсортированном массиве. Чтобы этого не происходило, давайте изменим направление последнего цикла на $n-1\ldots0$. Таким образом код становится следующим:
for i=0..n-1:
cnt[a[i]]++
pref[0] = 0
for i = 1..C:
pref[i] = pref[i - 1] + cnt[i]
for i=n-1..0:
res[pref[a[i]] - 1] = a[i]
pref[a[i]]--
Автор конспекта: Полина Романченко
По всем вопросам пишите в telegram @Romanchenko