Поразрядная сортировка :: Radix sort

Массив несколько раз перебирается и элементы перегруппировываются в зависимости от того, какая цифра находится в определённом разряде. После обработки разрядов (всех или почти всех) массив оказывается упорядоченным.При этом разряды могут обрабатываться в противоположных направлениях - от младших к старшим или наоборот.

Поразрядная сортировка по младшим разрядам

Элементы перебираются по порядку и группируются по самому младшему разряду (сначала все, заканчивающиеся на 0, затем заканчивающиеся на 1, ..., заканчивающиеся на 9). Возникает новая последовательность. Затем группируются по следующему разряду с конца, затем по следующему и т.д. пока не будут перебраны все разряды, от младших к старшим.

null

Точное название способа LSD radix sort (Least significant digit radix sorts) - поразрядная сортировка по наименьшей значащей цифре.

Поразрядная сортировка по старшим разрядам

Элементы перегруппироввываются по определённому разряду (сначала по самому старшему). Затем разбиваются на подгруппы в зависимости от значения этого разряда: равного 0, равного 1, равного 2, ..., равного 9. Каждая подгруппа обрабатывается отдельно, в ней к следующему разряду рекурсивно применяется radix sort.

null

Точное название способа 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)

Ссылки

Поразрядная сортировка

Radix sort

Реализация на различных ЯП