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

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

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

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

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

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

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

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

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

В алгоритмі використовуються два додаткових масиви: $C$ і $B$. Тому алгоритм потребує $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];
    }
}