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

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

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

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

При 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. Далее рекурсивно можно полностью аналогично перебрать получившиеся поддиапазоны массива, сравнивая значения второго и последующих разрядов, и переставляя элементы местами.

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

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

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

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

• Визуализатор1 — Java-аплет.
• Визуализатор2 — Java-аплет.
• Реализация алгоритма на C++.