R2. Очистить стопки

R6. Выполнить алгоритм Н

R3. Выделить /с-ю цифру ключа

R4. Откорректировать связи

R5. Перейти к следующей записи

Рис. 32. Поразрядная сортировка списка.

две переменные-указатели: ТОР [г] и В0ТМ[г], О < г < Л/, и, как и в главе 2, предполагается, что

LINK (LOG (ВОТМ [i] )) = ВОТМ [г] . (5)

R1. [Цикл по А;.] Вначале установить Р r- LOC(/?iv), указатель на последнюю запись. Затем выполнить шаги R2- R6 при А; = 1,2,... ,р (шаги R2-R6 составляют один "проход" - просмотр исходных данных) и завершить выполнение алгоритма. Переменная Р будет указывать на запись с наименьшим ключом, LINK(P) - на запись со следующим по величине ключом, LINK(LINK(P)) - на следующую запись и т. д. Поле LINK последней записи будет равно Л.

R2. [Очистить стопки.] При О < г < М установить ТОР [г] LOC(BOTM[i]) и

вотмю (- л.

R3. [Выделить А;-ю цифру ключа.] Пусть KEY(P) - ключ записи, на которую указывает Р, - равен (ai, аг,..., а). Установить г <- ар+\-к, к-ю младшую цифру этого ключа.

R4. [Откорректировать связи.] Установить LINK (ТОР [г]) <- Р и ТОР [г] Р.

R5. [Перейти к следующей записи.] Если А; = 1 (первый просмотр) и если Р = LOCiRj) при некотором j ф 1, установить Р <- LOC(/?j i) и возвратиться к шагу R3. Если А; > 1 (не первый просмотр), то установить Р LINK(P) и возвратиться к R3, если ? ф h..

R6. [Выполнить алгоритм Н.] (Теперь все элементы распределены по стопкам.) Выполнить приведенный ниже алгоритм Н, который "сцепляет" отдельные стопки в один список, подготавливая их к следующему просмотру. Установить Р <-ВОТМ СО], указатель на первый элемент объединенного списка (см. упр. 3).

Алгоритм Н {Сцепление очередей). Из М данных очередей со связями, удовлетворяющими соглашениям алгоритма R, данный алгоритм создает одну очередь, меняя при этом не более М связей. В результате ВОТМ СО] указывает на первый элемент и стопка О предпюствует стопке 1 ..., стопка М - 2 предшествует стопке М-1.

HI. [Начальная установка.] Установить i <- 0.

Н2. [Указатель на вершину стопки.] Установить Р <- ТОР [г].

НЗ. [Следующая стопка.] Увеличить г на 1. Если г М, то установить LINK(P) <- Л и завершить выполнение алгоритма.

Н4. [Стопка пуста?] Если ВОТМ[г] = Л, возвратиться к шагу НЗ.

Н5. [Сцепить стопки.) Установить LINK(P) <- ВОТМ[г]. Возвратиться к шагу Н2.

На рис. 33 показано содержимое стопок после каждого из трех просмотров, выполняемых при сортировке наших 16 чисел с М = 10. Алгоритм R очень просто запрограммировать в системе команд MIX, если найти удобный способ изменения операции на шагах R3 и R5 от одного просмотра к другому. В следующей программе этого удалось достичь, не жертвуя скоростью внутреннего цикла, путем предварительной записи двух команд в тело программы. Заметим, что ТОР [г] и ВОТМ [г] можно упаковать в одно слово.

ТОР СО] Т0Р[1] ТОР [2] ТОРЕЗ] ТОР [4] ТОР [5] ТОР [6] ТОР [7] ТОР [8] ТОР [9]

1512] б12

1тоз1

154 Т

275 765

14261

[897]

б77 Т

ВОТМЕО] В0ТМ[1] ВОТМ [2] ВОТМЕЗ] ВОТМ [4] ВОТМ [5] ВОТМ [6] ВОТМ [7] ВОТМ [8] ВОТМ [9]

Т0Р[О] Т0Р[1] ТОРИ ТОРЕЗ] ТОР [4] ТОРИ ТОР [6] ТОР [7] ТОР [8] ТОР [9] [5091

503 512 703 б12

Т Т Т

, , [275]

s s

653 061 170

/ч

ВОТМ[0] В0ТМ[1] ВОТМ [2] ВОТМЕЗ] ВОТМ [4] ВОТМ [5] ВОТМ [6] ВОТМ [7] ВОТМ [8] ВОТМ [9]

ТОР[0] Т0Р[1] ТОРИ ТОРЕЗ] ТОР [4] ТОР [5] ТОР [6] ТОР [7] ТОР [8] ТОР [9]

10611 Т

154. ,

15121

677 z1

509 653 [5031 16121

426 503 1612I 703 897

ВОТМЕО] В0ТМ[1] ВОТМ [2] ВОТМЕЗ] ВОТМ [4] ВОТМ [5] ВОТМ [6] ВОТМ [7] ВОТМ [8] ВОТМ [9]

Рис. 33. Поразрядная сортировка с использованием связного распределения памяти (показано содержимое всех десяти стопок после каждого просмотра).

Программа R {Поразрядная сортировка списков). Предполагается, что исходные ключи в ячейках по адресу от INPUT+1 до INPUT+N содержат р = 3 компоненты

(ui, йг, аз), хранящиеся в полях (1:1), (2:2) и (3:3) соответственно. (Таким образом, считается, что значение М меньше или равно размеру байта компьютера MIX.) В поле (4:5) каждой записи хранится связь LINK. Пусть ТОР [г] = PILES + г(1:2) и ВОТМ [г] = PILES -- г (4:5) при О < г < М. Удобно указывать в поле связи положение относительно адреса INPUT, так что LOC(BOTMCi]) = PILES -I- i - INPUT. Чтобы избежать появления отрицательных связей, нужно расположить таблицу PILES после таблицы INPUT. Значения индексных регистров таковы: гП = Р, г12 = г, г13 = 3 - к, г14 = ТОР [г]. Во время выполнения алгоритма Н г12 = г - М.

Время выполнения программы R равно 32iV -- 48М -- 38 - 4Е, где N - число исходных записей, М - основание системы счисления (число стопок), а.Е - число встретившихся пустых стопок. Сравнение с другими программами, построенными