Комбинаторные алгоритмы для программистов



             

Цифровая распределяющая сортировка


Цифровая распределяющая сортировка основана на наблюдении, что если имена уже отсортированы по младшим разрядами

l,l - 1,\ldots,1
, то их можно полностью отсортировать, сортируя только по старшим разрядам
p,p - 1,\ldots,i + 1
при условии, что сортировка осуществляется таким образом, чтобы не нарушить относительный порядок имен с одинаковыми цифрами в старших разрядах. Заметим, что к самой таблице обращаются по правилу "первым включается – первым исключается", и поэтому лучшим способом представления являются очереди. В частности, предположим, что с каждым ключом
x_i
ассоциируется поле связи
LINK_i
; тогда эти поля связи можно использовать для сцепления всех имен в таблице вместе во входную очередь
Q
. При помощи полей связи можно также сцеплять имена в очереди
Q_0,Q_1,\ldots,Q_{r - 1}
, используемые для представления стопок. После того как имена распределены по стопкам, очереди, представляющие эти стопки, связываются вместе для получения вновь таблицы
Q
. Алгоритм 15.4. представляет эту процедуру в общих чертах (очереди описаны в лекции 11). В результате применения алгоритма очередь
Q
будет содержать имена в порядке возрастания; то есть имена будут связаны в порядке возрастания полями связи, начиная с головы очереди
Q
.

Использовать поля связи

LINK_1,\ldots LINK_n
для формирования
x_1,\ldots,x_n
во входную очередь
Q

Алгоритм 15.4.Цифровая распределяющая сортировка

Алгоритм 15.4.Цифровая распределяющая сортировка




Содержание  Назад  Вперед