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

Сортування підрахунком(англ.counting sort) — алгоритм сортування цілих чисел в діапазоні від [math]0[/math] до деякої константи [math]k[/math] або складних об'єктів працює за лінійний час.

Зміст

Сортування цілих чисел [ред.]

Це найпростіший варіант алгоритму.

Опис [ред.]

Вихідна послідовність чисел довжини [math]n[/math], а в кінці відсортована, зберігається в масиві [math]A[/math]. Також використовується допоміжний масив [math]C[/math] з індексами від [math]0[/math] до [math]\mathrm k - 1[/math], що спочатку заповнюється нулями.

Послідовно пройдемо масивом [math]A[/math] і запишемо в [math]C[i][/math] кількість чисел, рівних [math]i[/math] .

Тепер достатньо пройти масивом [math]C[/math] і для кожного [math]number \in \[/math] в масив [math]A[/math] послідовно записати число [math]number\[/math] [ math] C[number][/math] раз.

Псевдокод [ред.]

Сортування складних об'єктів [ред.]

Сортування цілих чисел за лінійний час добре, але недостатньо. Іноді дуже бажано застосувати швидкий алгоритм сортування підрахунком для впорядкування набору будь-яких "складних" даних. Під "складними об'єктами" тут маються на увазі структури, що містять у собі кілька полів. Одне з них ми виділимо і назвемо ключем, сортування йтиме саме по ньому (передбачається, що значення, що приймаються ключем - цілі числа в діапазоні від [math] 0 [/ math] до [ math] \ mathrm k-1 [/ math] ).

Ми не зможемо використовувати тут точно той же алгоритм, що і для сортування підрахунком звичайних цілих чисел, тому що в наборі можуть бути різні структури, що мають однакові ключі. Існує два способиупоратися з цією проблемою — використовувати списки для зберігання структур у відсортованому масиві або заздалегідь порахувати кількість структур з однаковими ключами кожного значення ключа.

Опис [ред.]

Вихідна послідовність з [math]n[/math] структур зберігається в масиві [math]A[/math], а відсортована - в масиві [math]B[/math] того ж розміру. Крім того, використовується допоміжний масив [math]P[/math] з індексами від [math]0[/math] до [math]\mathrm k-1[/math].

Ідея алгоритму полягає в попередньому підрахунку кількості елементів з різними ключами у вихідному масиві та розділенні результуючого масиву на частини відповідної довжини (називатимемо їх блоками). Потім при повторному проході вихідного масиву кожен елемент копіюється в спеціально відведений його ключу блок, в першу вільну комірку. Це здійснюється за допомогою масиву індексів [math]P[/math] , в якому зберігаються індекси початку блоків для різних ключів. [math]P[key][/math] — індекс у результуючому масиві, який відповідає першому елементу блоку для ключа [math]key[/math] .

Пройдемо вихідним масивом [math]A[/math] і запишемо в [math]P[i][/math] кількість структур, ключ яких дорівнює [math]i[/math] .

Подумки розіб'ємо масив [math]B[/math] на [math]k[/math] блоків, довжина кожного з яких дорівнює відповідно [math]P[0][/math] , [math]P[1][/math ], . [math]P[k][/math] .

Тепер масив [math]P[/math] нам більше не потрібний. Перетворимо його на масив, що зберігає в [math]P[i][/math] суму елементів від [math]0[/math] до [math]i-1[/math] старого масиву [math]P[/math] .

Тепер "зрушимо" масив [math]P[/math] на елемент уперед: у новомумасив [math]P[0] = 0[/math] , а для [math]i \gt 0[/math] [math]P[i] = P_[i-1][/math] , де [math] ]P_[/math] - старий масив [math]P[/math]. Це можна зробити за один прохід масивом [math]P[/math] , причому одночасно з попереднім кроком. Після цієї дії в масиві [math]P[/math] будуть зберігатися індекси масиву [math]B[/math]. [math]P[key][/math] вказує початку блоку в [math]B[/math] , відповідного ключу [math]key[/math] .

Зробимо саме сортування. Ще раз пройдемо вихідним масивом [math]A[/math] і для всіх [math]i \in [0, n-1][/math] поміщатимемо структуру [math]A[i][/math] в масив [math]B[/math] на місце [math]P[A[i].key][/math] , а потім збільшувати [math]P[A[i].key][/math] на [math] 1[/math] . Тут [math]A[i].key[/math] - це ключ структури, що знаходиться в масиві [math]A[/math] на [math]i[/math] -тому місці.

Таким чином після завершення алгоритму [math]B[/math] буде міститися вихідна послідовність у відсортованому вигляді (так як блоки розташовані за зростанням відповідних ключів).

Варто також відзначити, що це сортування є стійким, так як два елементи з однаковими ключами будуть додані в тому ж порядку, в якому переглядалися у вихідному масиві [math]A[/math]. Завдяки цій властивості існує цифрове сортування.

Псевдокод [ред.]

Тут [math]A[/math] і [math]B[/math] - масиви структур розміру [math]n[/math], з індексами від [math]0[/math] до [math]n-1[ / Math] . [math]P[/math] — цілий масив розміру [math]k[/math] , з індексами від [math]0[/math] до [math]k-1[/math] , де [math]k[ /math] - кількість різних ключів.

Тут кроки 3 та 4 з опису об'єднані в один цикл. Звернітьувага, що в останньому циклі інструкцією

копіюється структура [math]A[i][/math] повністю, а не тільки її ключ.

Аналіз [ред.]

У першому алгоритмі перші два цикли працюють за [math] \ Theta (k) [/ math] і [math] \ Theta (n) [/ math] відповідно; подвійний цикл за [math] \ Theta (n + k) [/ math] . Алгоритм має лінійну тимчасову трудомісткість [Math] \ Theta (n + k) [/ Math]. Додаткова пам'ять, що використовується, дорівнює [math]\Theta(k)[/math] .

Другий алгоритм складається з двох проходів по масиву [math]A[/math] розміру [math]n[/math] та одного проходу по масиву [math]P[/math] розміру [math]k[/math] . Його трудомісткість, таким чином, дорівнює [Math] \ Theta (n + k) [/ Math]. Насправді сортування підрахунком можна буде застосовувати, якщо [math]k = O(n)[/math] , тому вважатимуться час роботи алгоритму рівним [math]\Theta(n)[/math] . Як і у звичайному сортуванні підрахунком, потрібно [math]\Theta(n + k)[/math] додаткової пам'яті - на зберігання масиву [math]B[/math] розміру [math]n[/math] та масиву [math]P[/math] розміру [math]k[/math] .

Алгоритм працює за лінійний час, але є псевдополіноміальним.

Пошук діапазону ключів [ред.]

Якщо діапазон значень не відомий заздалегідь, його можна знайти за допомогою лінійного пошуку мінімуму і максимуму у вихідному масиві, що не вплине на асимптотику алгоритму. Потрібно враховувати, що мінімум може бути негативним, у той час як у масиві [math]P[/math] індекси від [math]0[/math] до [math]k-1[/math]. Тому при роботі з масивом [math]P[/math] з вихідного [math]A[i][/math] необхідно віднімати мінімум, а при зворотному записі в [math]B[i][/math] додавати його.