Поразрядная сортировка :: Radix sort
Массив несколько раз перебирается и элементы перегруппировываются в зависимости от того, какая цифра находится в определённом разряде. После обработки разрядов (всех или почти всех) массив оказывается упорядоченным.При этом разряды могут обрабатываться в противоположных направлениях - от младших к старшим или наоборот.
Основная статья - Поразрядная LSD-сортировка по младшим разрядам
Элементы перебираются по порядку и группируются по самому младшему разряду (сначала все, заканчивающиеся на 0, затем заканчивающиеся на 1, ..., заканчивающиеся на 9). Возникает новая последовательность. Затем группируются по следующему разряду с конца, затем по следующему и т.д. пока не будут перебраны все разряды, от младших к старшим.
Точное название способа LSD radix sort (Least significant digit radix sorts) - поразрядная сортировка по наименьшей значащей цифре.
Основная статья - Поразрядная MSD-сортировка по старшим разрядам
Элементы перегруппироввываются по определённому разряду (сначала по самому старшему). Затем разбиваются на подгруппы в зависимости от значения этого разряда: равного 0, равного 1, равного 2, ..., равного 9. Каждая подгруппа обрабатывается отдельно, в ней к следующему разряду рекурсивно применяется radix sort.
Точное название способа MSD radix sort (Most significant digit radix sorts) - поразрядная сортировка по наибольшей значащей цифре.
MSD реализовывается несколько сложнее чем LSD, но при этом она эффективнее. При ориентации на наименьшие значащие цифры для всех элементов обрабатываются все разряды. А вот в случае наибольших значащих цифр рекурсия продолжается только до той глубины, до которой это необходимо, то есть пока у элементов подгруппы есть различия в определённом разряде.
Кроме того, MSD, в отличие от LSD, является устойчивым алгоритмом.
Разновидности
Лексографической вариацией поразрядной MSD-сортировкой является ABC-сортировка.
Характеристики алгоритма
| Название | Поразрядная сортировка (Radix sort) | |
|---|---|---|
| Автор | Гарольд Сьюард (Harold H. Seward) | |
| Год | 1954 | |
| Класс | Сортировки распределением | |
| Устойчивость | Нет (LSD) / Да (MSD) | |
| Сравнения | Нет | |
| Сложность по времени | Худшая | O(n × k) |
| Лучшая | O(n) | |
| Сложность по памяти | O(n + k) | |
Поразрядная сортировка
Реализация на различных ЯП