Стр. 92 - Основы алгоритмов и структур данных

90 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
5.4. Распределяющая сортировка (лексикографическая сортировка)
Данный алгоритм сортировки отличается от рассматривавшихся до сих пор
тем, что он основан не на сравнениях между именами, а на представлении
имен.
Мы полагаем, что каждое из имен x1 , x2 , …, xn имеет вид
) ,..., , ( 1, 1 , , i pi pi i x x x x− =
и их нужно отсортировать в возрастающем лексикографическом порядке,
т. е.
j j pj pj i pi pi i x x x x x x x x = < = − − ) ,..., , ( ) ,..., , ( 1, 1 , , 1, 1 , ,
тогда и только тогда, когда для некоторого t≤p имеем lj li x x, , = для l>t и
t ti x x <
, . (Например, слова в словаре упорядочены в лексикографическом
порядке).
Для простоты будем считать, что m x
li < ≤
, 0 , и поэтому каждое имя можно
представить как p m-ичных цифр. Чтобы не было имен разной длины, более
короткие имена дополняются нулями.
Распределяющая сортировка основана на наблюдении, что если имена уже
отсортированы по младшим разрядам l, l-1, ..., 1, то их можно полностью
отсортировать, сортируя только по старшим разрядам р, р—1, ..., l-1, при
условии, что сортировка осуществляется таким образом, чтобы не нарушить
относительный порядок имен с одинаковыми цифрами в старших разрядах.
Эта идея лежит в основе механических сортировальных устройств для
перфокарт.
Допустим, перфокарты состоят из k колонок. Вначале они сортируются по
k-й колонке, затем по (k-1)-й, потом по (k -2)-й и т.д. Каждая сортировка по
колонке состоит из чтения колонки каждой карты и физического перемещения
карты на верх стопки, которая отвечает цифре, находящейся в этой колонке
карты. Как только все карты помещены в соответствующие стопки, стопки
объединяются вместе в порядке возрастания; затем процесс повторяется для
следующей колонки слева. Эта процедура проиллюстрирована на примере
трехзначных десятичных чисел (рис 72). Стрелки на рисунке показывают, как
стопки имён объединяются в таблицу.