n = 9 и имеется цикл {Or 11 9l 8л 7r 8l Ir 2l 5l 4r). Этот цикл появляется в мультиграфе тогда и только тогда, когда перестановка со знаком начинается с 4 и содержит подцепочки 9187 и 25 или их реверсы. Все решения можно получить, если найти все перестановки со знаком множества {1,2,3,6} и заменить 1 значением 9187, 2 - значением 25. Значит, Ecfc < l/(2fe) 2=(ri + l)2"-*(ri - fe)!/2"n! = f (1/fe + l/(n + 1 - k)). Из этого следует, что Ее = J2k=i Ecfc + Ec„+i < Я„ + 1. Поскольку n + 1 - с - нижняя граница числа перебрасываний, нам понадобится >п + 1 - Ec>ri - Я„из них.

[В этом доказательстве использована идея В. Бафна (V. Bafna) и П. Певзнера (Р. Pevz-ner), SICOMP 25 (1996), 272-289, которые изучали более сложную проблему сортировки перестановки без знака посредством реверсирования. В этой задаче рассматривались перестановки, которые могут быть записаны в виде произведения неразрезанных циклов (1 2 3)(3 4 5)(5 6 7)..., оканчивающихся либо на (п-1 п), либо на (п-2 п-1 п) в зависимости от того, каким является п: четным или нечетным. Оказалось, что такие перестановки труднее всего сортировать.]

РАЗДЕЛ 5.2

1. Да; г и j могут изменяться в диапазоне 1 < j < г < Л в произвольном порядке. Это позволяет выполнять подсчет параллельно с вводом данных.

2. Сортировка будет устойчива в том смысле, как определено в начале этой главы, поскольку алгоритм, по существу, выполняет упорядочение в лексикографическом поряд-керазличающихся пар ключей {Ki,l), {К2, 2),..., {Kn,N). (Если представить себе, что к каждому ключу справа добавлен его адрес в файле, то равных ключей не будет, а значит, сортировка будет устойчива.)

3. Программа все-таки будет выполнять сортировку, но это будет неустойчивая сортировка. Если Kj = К{И j < i, то, в конце концов, Rj окажется после Ri. Кроме того, внесенные изменения замедлят работу программы С.

4. ENT1 N 1 STA OUTPUT+1,2 Л LD2 COUNT, 1 Л DEC1 1 Л LDA INPUT, 1 Л J1P ♦-4 Л I

5. Время выполнения уменьшится на А+1 - N-В машинных циклов, и это почти всегда можно рассматривать как существенное улучшение.

6. u = 0,v = 9..

После D1 COUNT =0000000000 После D2 COUNT = 2 2 1 0 1 3 3 2 1 1 После D4 COUNT = 2 4 5 5 6 9 12 14 15 16 Во время D5 COUNT = 2 3 5 5 5 8 9 12 15 16 j = 8

OUTPUT =------IG - 4A----5L 6A 6Т 61 70 7N----

После D5 OUTPUT = ОС 00 IN IG 2R 4A ST 5U 5L 6A 6T 61 70 7N 8S 9

7. Да; обратите внимание на то, что COUNT [iiTj] уменьшено на шаге D6, а затем уменьшается j.

8. Сортировка будет выполняться, но не будет устойчивой (см. упр. 7).

9. Пусть М = V - и; будем считать, что и и w умещаются в два байта. ЬОС(Л ,) = INPUT-1- j; LOC(COUNT[ji) = COUNT-1- j; LOG(Sy) = OUTPUT-1- j; rll = г; rl2 = j;ilZ = i-v или xl3 = Kj.

M EQU V-U

KEY EQU 0:2 (Сопутствующая информация в байтах 3:5)

2Н ЗН

5Н 6Н

ENN3 М 1

STZ C0UNT+V,3 М + 1

INC3 1 М + 1

J3NP *-2 М + 1

ENT2 N 1 LD3 INPUT,2(KEY) N

LDA COUNT,З N

INCA 1 N

STA COUNT,3 N

DEC2 1 N

J2P ЗВ N

ENN3 M-1 1

LDA COUNT+U 1

ADD C0UNT+V.3 M

STA C0UNT+V,3 M

INC3 1 M

J3NP 4B M

ENT2 N 1

LD3 INPUT,2(KEY) N

LDl COUNT.3 N

LDA INPUT,2 N

STA OUTPUT,1 N

DECl 1 N

STl COUNT,3 N

DEC2 1 N

J2P 6B N

DL Очистка COUNT. COUNT [u - fe] (- 0.

u < г < n. D2. Яикд i.

D3. Увеличить COUNT [ii:,].

N>j>0. D4. Накопление. rA (- COUNT [г - 1]. COUNT [г - 1] + COUNT [г] -> COUNT [г].

и < i <v. D5. Цикл j. D6. Вывод Ri. i (- COUNT [iiTj]. rA (- Rj. Si rA.

COUNT[iiTj] г - 1.

N>j>0. I Время выполнения - (ЮМ + 22 + 10) u.

10. Чтобы не использовать дополнительно N бит для "маркера" [см. раздел 1.3.3 и Cybernetics 1 (1965), 95] и при этом все-таки оставить время выполнения пропорциональным N, можно использовать следующий алгоритм, основанный на циклической структуре перестановки.

Р1. [Цикл по г.] Выполнить шаг Р2 для 1 < г < N; затем завершить выполнение процедуры.

Р2. [р(г) = г?] Выполнить шаги с РЗ по Р5, если p{i) ф i. РЗ. [Начало цикла.] Присвоить t «- j «- г.

Р4. [Обработать Rj\ Присвоить к (- p(j), Rj (- Rk, p{j) <- j, j (- fe. Если p{j) ф i, повторить этот шаг.

P5. [Конец цикла.] Присвоить Rj (- t, p{j) (- j.

Этот алгоритм изменяет р(г), поскольку в приложениях, использующих сортировку, можно считать, что р{г) хранится в оперативной памяти. С другой стороны, существуют приложения, такие как транспонирование матриц, в которых p{i) является функцией г, т. е. его для экономии памяти необходимо вычислять, а не считывать из таблицы. В этом случае можно использовать следующий метод, выполняя шаги от В1 до ВЗ для 1 < i < N.

81. Присвоить к «- р{г).

82. Если к > г, присвоить к «- р{к) и повторить этот шаг.

83. Если fe < г, ничего не выполнять, но если к = г (это означает, что г - наименьшее в своем цикле), то переставить операции цикла, связанные с г следующим образом.

•p(fc)

Присвоить t -i- Ri; затем, пока p{k) ф г, повторять присвоения Rk R к (- р{к); и, наконец, присвоить Rk t.

Этот алгоритм аналогичен процедуре, описанной в работе J. Boothroyd, Сотр. J. 10 (1967), 310,но требует меньшего количества операций перемещения данных; несколько усовершенствованный алгоритм предложил И. Д. Г. Мак-Леод (I. D. G. MacLeod) [Australian Сотр. J. 2 (1970), 16-19]. Анализ, выполненный для случайной перестановки в упр. 1.3.3-14, показывает, что шаг В2 выполняется в среднем (Л -1- 1)Hn - N раз. (См. также ссылки на литературу в ответе к упр. 1.3.3-12.) Аналогичный алгоритм можно разработать и для того, чтобы заменить (Лр(1),..., Др(л)) на [Ri,... ,Rn), например, если перекомпоновка в упр. 4 должна быть выполнена при условии OUTPUT = INPUT.

11. Пусть rll = г; г12 = j; г13 = к;тХ = t.

Время выполнения равно (17Л - 5A - 7B + 1)и, где А - число циклов в перестановке р(1)... p{N) и В - число неподвижных точек перестановки (единичных циклов). Получим

А = (mini, aveHN, maxN, dev \Ihn - Hn ) и В = (minO, avel, max Л, devl) для Л > 2 в соответствии с 1.3.3-(21) и 1.3.3-(28).

12. Очевидный способ - пройти по всему списку, заменяя связи к-го элемента числом к, и затем перекомпоновать элементы на втором проходе. Описанный ниже более прямой и быстрый способ для случая, когда записи не слишком велики, принадлежит М. Д. Мак-Ларену (М. D. MacLaren). (Для удобства предполагается, что О < LINK(P) < Л при 1 < Р < ЛГ, где Л = 0.)

Ml. [Инициализация.] Присвоить Р «- HEAD, «- 1.

М2. [Выполнено?] Если Р = Л (или, что равносильно, если к = N -\-1), выполнение процедуры заканчивается.

МЗ. [Обеспечить Р > к.] Если Р < к, присвоить Р (- LINK(P) и повторить этот шаг.

М4. [Обмен.] Поменять местами Rk и Л[Р]. (Предполагается, что LINK(fe) и LINK(P) также при этом меняются местами.) Затем присвоить Q LINK(fe), LINK(fe) (- Р, P4-Q, fe-(-fe-t-lH вернуться к шагу М2.

Доказательство состоятельности метода М. Д. Мак-Ларена может базироваться на проверке по индукции следующего свойства, которое всегда выполняется перед началом шага М2: элементы, которые >к в последовательности Р, LINK(P), LINK (LINK (Р)), ..., Л, - это oi.