Сортування за розрядами

Сортування за розрядами

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

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

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

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

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

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

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

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

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

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

#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