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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Сортування за розрядами
Клас Алгоритм сортування
Структура даних Масив
Найгірша швидкодія O(kN)
Просторова складність у найгіршому випадку O(k + N)

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

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

Ідея алгоритму[ред.ред. код]

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

Приклад роботи[ред.ред. код]

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

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

Посилання[ред.ред. код]