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

Поразрядная сортировка
Автор	Герман Холлерит
Предназначение	Алгоритм сортировки
Структура данных	Массив
Худшее время	$O(w\cdot n)$, где w — количество бит, требуемых для хранения каждого ключа.
Затраты памяти	$O(w+n)$
Медиафайлы на Викискладе

Поразрядная сортировка (англ. radix sort) — алгоритм сортировки, который выполняется за линейное время. Существуют стабильные варианты.

Исходно предназначен для сортировки целых чисел, записанных цифрами. Но так как в памяти компьютеров любая информация записывается целыми числами, алгоритм пригоден для сортировки любых объектов, запись которых можно поделить на «разряды», содержащие сравнимые значения, например, строки, и вообще любые данные, представленные в виде набора байтов.

Сравнение производится поразрядно: сначала сравниваются значения одного крайнего разряда, и элементы группируются по результатам этого сравнения, затем сравниваются значения следующего разряда, соседнего, и элементы либо упорядочиваются по результатам сравнения значений этого разряда внутри образованных на предыдущем проходе групп, либо переупорядочиваются в целом, но сохраняя относительный порядок, достигнутый при предыдущей сортировке. Затем аналогично делается для следующего разряда, и так до конца.

Так как выравнивать сравниваемые записи относительно друг друга можно в разную сторону, на практике существуют два варианта этой сортировки. Для чисел они называются в терминах значимости разрядов числа, и получается так: можно выровнять записи чисел в сторону менее значащих цифр (по правой стороне, в сторону единиц — LSD от англ. least significant digit) или более значащих цифр (по левой стороне, со стороны более значащих разрядов — MSD от most significant digit).

При LSD-сортировке получается порядок, уместный для чисел. Например: 1, 2, 9, 10, 21, 100, 200, 201, 202, 210. То есть, здесь значения сначала сортируются по единицам, затем сортируются по десяткам, сохраняя отсортированность по единицам внутри десятков, затем по сотням, сохраняя отсортированность по десяткам и единицам внутри сотен, и так далее.

При MSD-сортировке получается алфавитный порядок, который уместен для сортировки строк текста. Например «b, c, d, e, f, g, h, i, j, ba» отсортируется как «b, ba, c, d, e, f, g, h, i, j». Если MSD применить к числам, то получится алфавитный, но не числовой порядок: 1, 10, 100, 2, 200, 201, 202, 21, 210, 9.

Накапливать при каждом проходе сведения о группах можно разными способами — например в списках, в деревьях, в массивах, выписывая в них либо сами элементы, либо их индексы.

Существует нестабильный вариант рекурсивной побитовой сортировки, выполняющейся непосредственно в сортируемом массиве: на первом проходе движение идёт навстречу друг другу, в начале массива ищется элемент с 1 в первом битовом разряде, в конце массива ищется элемент с 0 в том же разряде. Найденные элементы меняются местами, и так до тех пор, пока рассматриваемые индексы не встретятся. Таким образом в начале массива, до места встречи индексов, собираются все элементы с битом равным 0, а после этого индекса — все элементы с равным 1. Далее рекурсивно можно полностью аналогично перебрать получившиеся поддиапазоны массива, сравнивая значения второго и последующих разрядов, и переставляя элементы местами.

Оценка сложности

Время работы алгоритма поразрядной сортировки равно $O(n\omega )$, где $n$ - количество ключей в исходном массиве, а $\omega$ - их длина. LSD варианты сортировки могут достигать нижней границы $\omega$ как средней длины ключей, группируя их по похожим длинам и сортируя группы по отдельности.

Применение для строк в варианте с корзинной сортировкой

Для сортировки по очередному разряду может применяться корзинная сортировка. Каждый разряд проходится по два раза. На первом проходе подсчитывается количество тех или иных значений в этом разряде. Затем для каждого возможного значения подготавливаются массивы для хранения элементов с этим значением. При втором проходе выписываются сами элементы в эти массивы. Эффективная реализация возможна при использовании массива ссылок на строки вместо самих строк, и дополнительного массива «размеров корзин», инициализируемого при первом проходе числом элементов в каждой «корзине».

Второй и последующие проходы выполняются отдельно над каждой корзиной, полученной на предыдущем проходе, с делением её на «подкорзины» и сравнением соответственно второго и последующих символов строк.

Операция завершается при достижении максимальной длины строки или когда все «подкорзины» получили длину 1.

Литература

• Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 192—201. — ISBN 5-8459-0082-4.