Цифровая сортировка.

Задана последовательность целых чисел а₁, а₂, …, а_n, каждое из которых заключено в интервале [0, m-1].

Если число m не слишком велико, то заданную последовательность можно упорядочить следующим образом:

1. организуем m пустых очередей по одной для каждого целого числа от 0 до m-1. Каждую такую очередь назовём черпаком.

2. Просмотрим последовательность а₁, а₂, …, а_n слева на право, помещая элемент а_i в очередь с номером а_i.

3. Сцепим эти очереди (содержимое (i+1)-ой очереди приписываем к концу i-ой очереди) и получим в результате упорядоченную последовательность.

Т.к. любой элемент можно поместить в i-ю очередь за постоянное время, то n элементов можно поместить в очереди за время O(n). Сцепление m очередей требует времени порядка O(m). Если m=O(n), то этот алгоритм сортирует n целых чисел за время порядка O(n). Назовём этот алгоритм сортировкой вычерпыванием.

Рассмотрим пример такой сортировки.

Сортировка поразрядным группированием. Эта сортировка начинается с анализа самой младшей значащей цифры ключевого слова. Затем все величины с одинаковыми значащими цифрами объединяются в группы.

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

Система счисления с основанием p требует p групп (очередей или черпаков).

Например:

Исходная таблица	Первое распределение	Объеди-нение	Второе распределение	Объеди-нение
19 13 05 27 01 26 31 16 02 09 11 21	– 01,31,11,21 02 13 – 05 26,16 27 – 19,09	01 31 11 21 02 13 05 26 16 27 19 09	01,02,05,09 11,13,16,19 21,26,27 31 – – – – – –	01 02 05 09 11 13 16 19 21 26 27 31

Следующим обобщением сортировки вычёрпыванием будет распространение её на кортежи неодинаковой длины, которые мы будем называть цепочками.

Если самая длинная цепочка имеет длину k, то можно любую цепочку дополнить специальным символом до длины k и затем применять алгоритм поразрядного группирования (или как его ещё называют – алгоритм лексико-графической сортировки).

Следующим обобщением сортировки вычёрпыванием будет распространение её на кортежи неодинаковой длинны, которые мы будем называть цепочками.

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

Рассмотрим алгоритм, сортирующий n-элементную последовательность цепочек различной длинны, компонентами которых служат числа между 0 и m-1; время работы этого алгоритма на такой последовательности равно О(m+l*), где l_i – длина i-ой цепочки, а l*= . Этот алгоритм полезен в ситуации, когда числа m и l* имеют одинаковый порядок O(n).

Суть этого алгоритма в том, что сначала он сначала располагает цепочки в порядке убывания длин. Пусть l_max – длина самой длинной цепочки. Тогда сортировка вычёрпыванием применяется l_max раз.

Но первое такое применение (по самой правой компоненте) сортируют лишь цепочки длины l_max. Второе применение сортирует (в соответствии с (l_max – 1)-й компонентой) те цепочки, длина которых не менее l_max – 1, и т.д.

Вход: Последовательность цепочек (кортежей) А₁, А₂, …, А_n, компоненты которых представлены целыми числамии от 1 до m – 1. Пусть l_i – длина цепочки A_i = (a_i1, a_i2, … , a_ili) и l_max – наибольшее из чисел l_i.

Выход: Перестановка В₁, В₂, …, В_n цепочек A_i такая, что В₁ ≤ В₂ ≤ … ≤ В_n .

Метод:

1. формирование списков симвролов, которые появляются в l компоненте одной или более цепочек. Строим пары (l, a_il) – для каждой компоненты каждой цепочки. Затем сформируем упорядоченный список: НЕПУСТ[l].

2. Определяем длину каждой цепочки, формируем список ДЛ[l], в котором содержатся указатели всех цепочек длины l.

3. Сортируем цепочки по компонентам, как в предыдущих алгоритмах с учётом списков НЕПУСТ и ДЛ.

Алгоритм описанного метода:

СОРТИРОВКА_ЦЕПОЧЕК_РАЗЛИЧНОЙ_ДЛИНЫ(A, l)4

для l от 1 до l_max

делать

НЕПУСТ[l] ← U А_i[l]

НЕПУСТ[l] ← упорядоченный НЕПУСТ[l]

для l от 1 до l_max

делать ДЛ[l] ← U А_i[1:l]