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

Данный метод является обобщением карманной сортировки. Пусть известно, что каждый ключ является k–разрядным целым числом. Например, если k = 4, то все ключи находятся в диапазоне 0000 – 9999. Смысл поразрядной сортировки заключается в том, что k раз повторяется карманная сортировка. На первом шаге все ключи группируются по младшей цифре (разряд единиц). Для этого в каждом ключе выделяется младшая цифра и элемент помещается в соответствующий список-карман для данной цифры. Потом все списки объединяются и создается новый массив, в котором элементы упорядочены по младшей цифре ключа. К этому массиву опять применяется карманная сортировка, но уже по более старшей цифре (разряд десятков): в каждом ключе выделяется вторая справа цифра и элементы распределяются по соответствующим спискам. Потом списки объединяются в массив, где элементы будут упорядочены уже по двум младшим цифрам. Процесс распределения по все более старшим цифрам с последующим объединением повторяется до старшей цифры (разряд k).

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

Пример. Пусть имеется исходный набор из 15-ти двухразрядных ключей (k=2):

56, 17, 83, 09, 11, 27, 33, 02, 16, 45, 08, 37, 66, 99, 90

Первый шаг: выделяем младшую цифру и распределяем ключи по десяти спискам:

ключ 56 в список для цифры 6, ключ 17 в список для цифры 7, ….., ключ 16 опять в список для цифры 6 и т.д.

90 11 02 83 45 56 17 08 09

33 16 27 99

66 37

Объединяем списки: 90, 11, 02, 83, 33, 45, 56, 16, 66, 17, 27, 37, 08, 09, 99

В этом наборе ключи упорядочены по младшей цифре

Второй шаг: выделяем старшую цифру (десятки) и распределяем ключи по своим спискам:

ключ 90 в список для 9, ключ 11 в список для 1, ключ 02 в список для 0 и т.д.

02 11 27 33 45 56 66 83 90

08 16 37 99

09 17

Объединение этих списков дает отсортированный набор:

02, 08, 09, 11, 16, 17, 27, 33, 37, 45, 56, 66, 83, 90, 99

Для программной реализации необходимо объявить десятиэлементный массив и ссылочный тип для организации списков. Удобно вместе с началом каждого списка хранить указатель на его последний элемент, что упрощает как добавление новых элементов в конец списка, так и объединение отдельных списков. Внешний цикл алгоритма повторяется k раз (разрядность ключа). Каждый раз внутри этого цикла необходимо:

· обнулить все 20 указателей

· циклом по числу элементов (m) распределить элементы по своим спискам, выделяя в ключе необходимую цифру

· циклом по 10 объединить списки в новый набор данных

В целом, поразрядная сортировка не эффективна при малых объемах входных данных, но чем больше этот объем, тем выше эффективность метода. Трудоемкость пропорциональна объему входных данных, что лучше чем у быстрой сортировки. Платой за это являются дополнительные затраты памяти для поддержки вспомогательных списков.

Интересно отметить, что данный метод очень хорошо подходит для современных архитектур вычислительных систем с конвейерной обработкой данных и использованием нескольких процессоров.