Сортування за розрядами англ Radix sort швидкий стабільний алгоритм впорядкування даних Застосовується для впорядкування

Сортування за розрядами (англ. Radix sort) — швидкий стабільний алгоритм впорядкування даних. Застосовується для впорядкування елементів, що є ланцюжками над будь-яким скінченним алфавітом (напр. рядки, або цілі числа). Як допоміжний використовує будь-який інший стабільний алгоритм сортування.

Сортування за розрядами
Клас	Алгоритм сортування
Структура даних	Масив
Найгірша швидкодія	$O(kN)$
Просторова складність у найгіршому випадку	$O(k+N)$

Алгоритм застосовувався для впорядкування перфокарт.

Ефективність

Тема ефективності сортування за розрядами в порівнянні з іншими алгоритмами сортування дещо заплутана і є об'єктом багатьох непорозумінь. Те, чи сортування за розрядами більш, менш або так само ефективне як і найкращі алгоритми сортування порівняннями, залежить від того, які припущення зроблено. Часова складність сортування за розрядами $O (wn)$ для $n$ ключів, цілих розміром в машинне слово $w$ . Іноді $w$ представляють як сталу, що може зробити сортування за розрядами привабливішим (для достатньо великого $n$ ), ніж найкращі алгоритми сортування порівняннями, які виконуються за $O (n log n)$ порівнянь, щоб відсортувати $n$ ключів. Однак, у загальному випадку $w$ не можна вважати сталою: якщо всі $n$ ключів різні, тоді $w$ має бути щонайменше $log n$ для RAM-машини, щоб бути в стані зберігати їх в пам'яті, що дає найкращу швидкодію $O (n log n)$ . Тут може здатись, що сортування за розрядами не може бути ефективнішим, ніж найкращі алгоритми порівняння (навіть гірше, якщо ключі значно довші, ніж $log n$ ).

Контраргументом є те, що швидкодія сортування порівняннями вимірюються кількістю порівнянь, а не часом виконання. З деякими припущеннями порівняння в середньому вимагатимуть сталого часу, а з іншими припущеннями ні. Порівняння випадково згенерованих ключів потребує в середньому сталого часу, бо ключі відмінні в першому є біті у половині випадків і відмінні в другому біті у половині другої половини, і т.д. Що дає в середньому два біти, які треба порівняти. В сортувальних алгоритмах перші порівняння задовольняють умові випадковості, але з поступом алгоритму порівнювані ключі більше не випадково вибрані.

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

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

Приклад роботи

В прикладі показано, як впорядковувати таким алгоритмом масив трицифрових чисел:

572 572 523 266 266 523 349 349 783 --> 783 --> 266 --> 523 523 266 572 572 349 349 783 783 ^ ^ ^

Аналіз

Час роботи кожного циклу сортування залежить від того алгоритму, що використовується як допоміжний. Найчастіше використовують сортування підрахунком, що працює за час $\;O(N+K)$ (де N — кількість елементів в масиві; K — кількість символів у алфавіті, якщо впорядковуються десяткові числа, то K = 10) і використовує додатково $\;O(N+K)$ пам'яті. Всього здійснюється стільки циклів впорядкування, скільки розрядів у максимальному елементі.

Загальна складність роботи алгоритму з використанням сортування підрахунком є $O(D\cdot \;(N+K))$ (D — кількість розрядів). Якщо впорядковувати цим алгоритмом цілі числа, то складність буде $\;O(N\log M)$ , де M — найбільший елемент масиву.

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

#include <iostream> #include <random> #include <limits> #include <vector> using namespace std; template<typename IntegerType> void radix_sort(vector<IntegerType>& elems,  size_t max = numeric_limits<IntegerType>::max(),  size_t base = 256) {  vector< vector<IntegerType> > buckets(base);  for (size_t b = 1; b < max; b *= base)  {  for( auto& bucket : buckets) { bucket.clear(); }    for (auto cur : elems)  {  buckets[ (cur / b) % base].push_back(cur);  }    elems.clear();  for( auto& bucket : buckets)  {  elems.insert(elems.end(), bucket.begin(), bucket.end());  }  } } //An example of usage int main() {  vector<int> elems;    //fill elems with random data  random_device rd;  mt19937 mt(rd());  uniform_real_distribution<double> dist(1, 100);  for (size_t i = 0, size = 24; i < size; ++i)  {  elems.push_back(dist(mt));  }    radix_sort(elems);    for (auto x : elems) { cout << x << ' '; }  return 0; }

Примітки

Nilsson, Stefan (1 квітня 2000). The fastest sorting algorithm?. . 311: 38—45.

Посилання

Чи швидше сортування за розрядами ніж швидке сортування на цілочисельних масивах? (англ.)

Джерела

Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press.

[1] Nilsson, Stefan (1 квітня 2000). The fastest sorting algorithm?. . 311: 38—45.