Сортування за розрядами () — швидкий стабільний алгоритм впорядкування даних. Застосовується для впорядкування елементів, що є ланцюжками над будь-яким скінченним алфавітом (напр. рядки, або цілі числа). Як допоміжний використовує будь-який інший стабільний алгоритм сортування.
Алгоритм застосовувався для впорядкування перфокарт.
Ефективність
Тема ефективності сортування за розрядами в порівнянні з іншими алгоритмами сортування дещо заплутана і є об'єктом багатьох непорозумінь. Те, чи сортування за розрядами більш, менш або так само ефективне як і найкращі алгоритми сортування порівняннями, залежить від того, які припущення зроблено. Часова складність сортування за розрядами для ключів, цілих розміром в машинне слово . Іноді представляють як сталу, що може зробити сортування за розрядами привабливішим (для достатньо великого ), ніж найкращі алгоритми сортування порівняннями, які виконуються за порівнянь, щоб відсортувати ключів. Однак, у загальному випадку не можна вважати сталою: якщо всі ключів різні, тоді має бути щонайменше для RAM-машини, щоб бути в стані зберігати їх в пам'яті, що дає найкращу швидкодію . Тут може здатись, що сортування за розрядами не може бути ефективнішим, ніж найкращі алгоритми порівняння (навіть гірше, якщо ключі значно довші, ніж ).
Контраргументом є те, що швидкодія сортування порівняннями вимірюються кількістю порівнянь, а не часом виконання. З деякими припущеннями порівняння в середньому вимагатимуть сталого часу, а з іншими припущеннями ні. Порівняння випадково згенерованих ключів потребує в середньому сталого часу, бо ключі відмінні в першому є біті у половині випадків і відмінні в другому біті у половині другої половини, і т.д. Що дає в середньому два біти, які треба порівняти. В сортувальних алгоритмах перші порівняння задовольняють умові випадковості, але з поступом алгоритму порівнювані ключі більше не випадково вибрані.
Ідея алгоритму Ідея полягає в тому, щоб спочатку впорядкувати всі елементи за молодшим розрядом, потім стабільно впорядкувати за другим розрядом, потім за третім і так далі аж до найстаршого. Оскільки, припускається, що кожен розряд приймає значення з невеликого діапазону, то кожен цикл впорядкування можна виконувати швидко і з малими затратами пам'яті.
Приклад роботи В прикладі показано, як впорядковувати таким алгоритмом масив трицифрових чисел: 572 572 523 266 266 523 349 349 783 --> 783 --> 266 --> 523 523 266 572 572 349 349 783 783 ^ ^ ^
Аналіз Час роботи кожного циклу сортування залежить від того алгоритму, що використовується як допоміжний. Найчастіше використовують сортування підрахунком, що працює за час (де N — кількість елементів в масиві; K — кількість символів у алфавіті, якщо впорядковуються десяткові числа, то K = 10) і використовує додатково пам'яті. Всього здійснюється стільки циклів впорядкування, скільки розрядів у максимальному елементі.
Загальна складність роботи алгоритму з використанням сортування підрахунком є (D — кількість розрядів). Якщо впорядковувати цим алгоритмом цілі числа, то складність буде , де 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; }
Примітки
Посилання Чи швидше сортування за розрядами ніж швидке сортування на цілочисельних масивах?
Джерела Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1