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

Сортування за розрядами
Клас	Алгоритм сортування
Структура даних	Масив
Найгірша швидкодія
Просторова складність у найгіршому випадку

Сортування за розрядами (англ. 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
          ^      ^      ^

Аналіз

Час роботи кожного циклу сортування залежить від того алгоритму, що використовується як допоміжний. Найчастіше використовують сортування підрахунком, що працює за час $\;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?. Dr Dobb's Journal 311: 38–45.

Посилання

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

Джерела

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Nilsson, Stefan (1 квітня 2000). The fastest sorting algorithm?. Dr Dobb's Journal 311: 38–45.