Сортировка подсчетом: различия между версиями
м |
м |
||
Строка 28: | Строка 28: | ||
[[Категория:Другие сортировки]] | [[Категория:Другие сортировки]] | ||
− | + | [[Категория:Конспект]] | |
{{Автор|Полина Романченко|Romanchenko}} | {{Автор|Полина Романченко|Romanchenko}} |
Версия 21:08, 13 августа 2019
Описание алгоритма
Если количество возможных различных элементов в множестве относительно невелико, то сортировка подсчетом является одним из самых оптимальных решений.
Главная идея алгоритма: посчитать количество элементов каждого типа, а затем выставить нужное количество элементов первого по порядку типа, затем второго и так далее.
Например, если даны натуральные числа от $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