Сортування підрахунком
Сортування підрахунком[1] (англ. Counting sort) — алгоритм впорядкування, що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві так і від кількості різних елементів.
Ідея алгоритму полягає в наступному: спочатку підрахувати скільки разів кожен елемент (ключ) зустрічається в вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за один прохід поставити всі елементи на свої місця.
Для простоти будемо вважати, що всі елементи (ключі) є натуральними числами що лежать в діапазоні Процедура виконує сортування масиву :
1 — масив з K елементів, заповнений нулями 2 for to 3 do 4 // Зараз містить кількість елементів, що дорівнюють 5 for to 6 do 7 // Зараз містить кількість елементів менших або рівних 8 for downto 9 do 10 11
![{\displaystyle length[A]\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d7dc5151d133b0e8a4e528da3f5c515436c59cf)
![{\displaystyle C[A[i]]\gets \;C[A[i]]+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf4b30cd9778b1eef719d0fadfc916731d86aced)
![{\displaystyle C[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9e670bd48c5b92b5228727d2a35097581cc85a6)
![{\displaystyle C[i]\gets \;C[i]+C[i-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a285d14e687a3ada2f661dc74ca22a33c6fa225)
![{\displaystyle i\gets \;length[A]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f757dbfc3f5423593b8c744ced5b8fde1acf8df)
![{\displaystyle B[C[A[i]]]\gets \;A[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43e055bd1e90f545feccd8946e58dfaac90929aa)
![{\displaystyle C[A[i]]\gets \;C[A[i]]-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb4652457c75cb60061446c0e03862c7740d0bbb)
В алгоритмі присутні тільки прості цикли: в рядках 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.
| ||||||||||||||||||||||||||||
