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

Материал из Algocode wiki
Версия от 11:11, 26 сентября 2020; Forestryks (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

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

Например, если даны натуральные числа от $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]. Посмотрим, что будет происходить с каждой итерацией последнего цикла.

  1. $i = 0,\ pref[a[i].first] - 1 = 1 \Longrightarrow res = \text{[null, \{1, 'a'\}, null]},\ pref = [0, 1, 2, 3]$
  2. $i = 1,\ pref[a[i].first] - 1 = 2 \Longrightarrow res = \text{[null, \{1, 'a'\}, \{3, 'b'\}]},\ pref = [0, 1, 2, 2]$
  3. $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