Сортування підрахунком
Сортування підрахунком[1] (англ. Counting sort) — алгоритм впорядкування, що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві так і від кількості різних елементів.
Ідея алгоритму полягає в наступному: спочатку підрахувати скільки разів кожен елемент (ключ) зустрічається в вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за один прохід поставити всі елементи на свої місця.
Для простоти будемо вважати, що всі елементи (ключі) є натуральними числами що лежать в діапазоні Процедура виконує сортування масиву :
1 — масив з K елементів, заповнений нулями 2 for to 3 do 4 // Зараз містить кількість елементів, що дорівнюють 5 for to 6 do 7 // Зараз містить кількість елементів менших або рівних 8 for downto 9 do 10 11
В алгоритмі присутні тільки прості цикли: в рядках 2, 6, 9 — цикл довжини N (довжина масиву), в рядку 4 — цикл довжини 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];
}
}
- ↑ Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Розділ 8.2: Сортування підрахунком. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.