Поразрядная сортировка :: 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 on Wikipedia
Реализация на различных ЯП

Добавить комментарий