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

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

Клас	Алгоритм сортування
Структура даних	Масив
Найгірша швидкодія	$O(kN)$
Просторова складність у найгіршому випадку	$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). Тут може здатись, що сортування за розрядами не може бути ефективнішим, ніж найкращі алгоритми порівняння (навіть гірше, якщо ключі значно довші, ніж 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;
}

Посилання

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

Джерела

• Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1