Сортування підрахунком
Матеріал з Вікіпедії — вільної енциклопедії.
Сортування підрахунком (англ. Counting sort) — алгоритм впорядкування, що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві так і від кількості різних елементів.
[ред.] Ідея алгоритму
Ідея алгоритму полягає в наступному: спочатку підрахувати скільки разів кожен елемент (ключ) зуcтрічається в вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за один прохід поставити всі елементи на свої місця.
[ред.] Псевдокод алгоритму
Для простоти будемо вважати, що всі елементи (ключі) є натуральними числами що лежать в діапазоні 1..K. Процедура 
виконує сортування масиву 
:
— масив з K елементів, заповнений нулями 2 for
to
3 do
4 for
to
5 do
6 for
downto
7 do
8
9
[ред.] Аналіз алгоритму
В алгоритмі присутні тільки прості цикли: в рядках 2, 6, 9 — цикл довжини N (довжина масиву), в рядку 4 — цикл довжини K (величина діапазону). Отже складність роботи алгоритму є 
.
В алгоритмі використовуються два додаткових масиви: і 
. Тому алгоритм потребує додаткової пам'яті.
В такій реалізації алгоритм є стабільним. Саме ця його властивість дозволяє використовувати його як частину інших алгоритмів сортування (напр. сортування за розрядами).
Використання даного алгоритму є доцільним тільки у випадку малих K (порядку N).
