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

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

Ідея алгоритму

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

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

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

${\displaystyle \;Counting\_Sort(A)}$ 1 ${\displaystyle \;C}$ — масив з K елементів, заповнений нулями 2 for ${\displaystyle i\gets \;1}$ to ${\displaystyle length[A]\;}$ 3 do ${\displaystyle C[A[i]]\gets \;C[A[i]]+1}$ 4 // Зараз ${\displaystyle C[i]}$ містить кількість елементів, що дорівнюють ${\displaystyle i}$ 5 for ${\displaystyle i\gets \;2}$ to ${\displaystyle K\;}$ 6 do ${\displaystyle C[i]\gets \;C[i]+C[i-1]}$ 7 // Зараз ${\displaystyle C[i]}$ містить кількість елементів менших або рівних ${\displaystyle i}$ 8 for ${\displaystyle i\gets \;length[A]}$ downto ${\displaystyle 1\;}$ 9 do ${\displaystyle B[C[A[i]]]\gets \;A[i]}$ 10 ${\displaystyle C[A[i]]\gets \;C[A[i]]-1}$ 11 ${\displaystyle A\gets \;B}$ 

Аналіз алгоритму

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

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

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

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

Приклад реалізації на С++

#include <vector> #include <algorithm> using namespace std; void counting_sort(vector<int>& elems, int min, int max) {  if (elems.empty() || min > max)  {  return;  }    vector<unsigned> counts(max - min + 1);    for (int elem: elems)  {  ++counts[elem - min];  }    auto elemsIt = elems.begin(); //current position to write result  for (int i = min; i <= max; ++i)  {  // write counts[i - min] copies of i into elems  fill_n(elemsIt, counts[i - min], i);  elemsIt += counts[i - min];  } } 

Примітки

1. Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Розділ 8.2: Сортування підрахунком. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .