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

Матеріал з Вікіпедії — вільної енциклопедії.

Сортування за розрядами (англ. 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 — найбільший елемент масиву.