Сортування підрахунком

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Сортування підрахунком (англ. Counting sort) — алгоритм впорядкування, що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві так і від кількості різних елементів.

Ідея алгоритму[ред.ред. код]

Ідея алгоритму полягає в наступному: спочатку підрахувати скільки разів кожен елемент (ключ) зустрічається в вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за один прохід поставити всі елементи на свої місця.

Псевдокод алгоритму[ред.ред. код]

Для простоти будемо вважати, що всі елементи (ключі) є натуральними числами що лежать в діапазоні 1..K. Процедура \;Counting\_Sort(A) виконує сортування масиву \;A:

\;Counting\_Sort(A)
1 \;C — масив з K елементів, заповнений нулями
2 for i\gets\;1 to length[A]\;
3     do C[A[i]]\gets\;C[A[i]]+1
4 for i\gets\;2 to K\;
5     do C[i]\gets\;C[i]+C[i-1]
6 for i\gets\;length[A] downto 1\;
7     do B[C[A[i]]]\gets\;A[i]
8        C[A[i]]\gets\;C[A[i]]-1
9 A\gets\;B

Аналіз алгоритму[ред.ред. код]

В алгоритмі присутні тільки прості цикли: в рядках 2, 6, 9 — цикл довжини N (довжина масиву), в рядку 4 — цикл довжини K (величина діапазону). Отже складність роботи алгоритму є \;O(N + K).

В алгоритмі використовуються два додаткових масиви: \;C і \;B. Тому алгоритм потребує \;O(N + K) додаткової пам'яті.

В такій реалізації алгоритм є стабільним. Саме ця його властивість дозволяє використовувати його як частину інших алгоритмів сортування (напр. сортування за розрядами).

Використання даного алгоритму є доцільним тільки у випадку малих K (порядку N).

Джерела[ред.ред. код]

  • Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1