02, ..., un+i-k, где Ri < < Rk-1 < Rai < • < Ra+i-k - требуемый окончательный порядок записей. Далее, LINKCj) > j для 1 < j < fe, так что из равенства LINK(j) = Л следует j > fe.

Довольно интересно проанализировать алгоритм М. Д. Мак-Ларена. Одно из его замечательных свойств состоит в том, что алгоритм можно выполнить в обратном порядке и восстановить исходное множество связей из конечных значений LINK(l) ... LINKCN). Каждая из N\ возможных конфигураций на выходе при j < LINK(j) < N соответствует в точности одной из N] возможных конфигураций на входе. Если обозначить через А количество операций Р (- LINK(P) на шаге МЗ, то N - А - число индексов j, таких, что LINK(j) = j после завершения выполнения процедуры. Это возникает тогда и только тогда, когда j наибольшее в своем цикле; следовательно, N - A равно числу циклов перестановки, а Л = (minО, ave N - Hn, max N-1).

См. М. D. MacLaren, JACM 13 (1966), 404-411; D. Cries, J. F. Prins, Science of Computer Programming 8 (1987), 139-145. 13. D5. Присвоить r (- N.

D6. Если r = 0, остановиться. В противном случае, если COUNT[iiTr] < г, присвоить г <- г - 1 и повторить этот шаг; если COUNT[iiTr] = г, уменьшить и COUNT[iiTr], и г на 1 и повторить этот шаг. В противном случае присвоить Л «- Д,, j <-COUNT[АГг] , COUNT[АГг] <-j-l.

D7. Присвоить S <- Rj,k<r- COUNTCATy], COUNlCATj] <- к - 1, Rj <- R, R <- S, j fe. Затем, если j ф г, повторить этот шаг; если j = г, присвоить Rj (- Л, г (- г - 1 и вернуться к шагу D6.

Для того чтобы убедиться в состоятельности этой процедуры, обратите внимание, что перед началом шага D6 все записи Rj, которые еще не находятся на своих окончательных местах и для которых j > г, должны продвинуться влево; когда г = О, не может существовать ни одна такая запись, поскольку нечему двигаться вправо. Алгоритм, конечно, очень элегантен, но, к сожалению, нестабилен при наличии равных ключей. Он тесно связан с построением Фоаты в теореме 5.1.2В.

РАЗДЕЛ 5.2.1

1. Да. Равные элементы никогда не меняются местами.

2. Да, но в случае, если имеются равные элементы, время работы увеличится и процесс сортировки будет выполняться в прямо противоположном направлении по сравнению с устойчивой сортировкой.

3. Предполагается, что следующая программа из 8 команд - самая короткая программа сортировки для машины MIX, хотя она и не может быть рекомендована из-за низкой скорости выполнения. Считается, что числа находятся в ячейках 1,..., 7V (т. е. INPUT EQU 0); в противном случае нужна еще одна команда.

Замечание. Чтобы оценить время выполнения, заметим, что А равно числу инверсий, а величина В - довольно простая функция таблицы инверсий и (в предположении, что

элементы ввода различны и расположены в случайном порядке) имеет производящую функцию

z-\\ + z){\ + z + z+)

X (1 + / + z+ + z++)... (1 + z"- + z"- + . • • + г(-)/=)/Я!.

Среднее значение В равно - 1 + ELiC " 1)(2 - 1)/6 = (Л - 1)(4ЛГ2 + дг + зб)/36; следовательно, среднее время выполнения - примерно Nu.

4. Рассмотрим таблицу инверсий Bi ... Bn данной исходной перестановки в смысле упр. 5.1.1-7. Величина А на единицу меньше числа элементов Bj, которое равно j - 1, а В равно сумме элементов Bj. Следовательно, обе величины - В - Л и В - достигают максимума, когда исходная перестановка равна Л... 2 1; обе величины достигают минимума, когда исходная перестановка равна 1 2. ..N. Следовательно, минимальное возможное время выполнения достигается при Л = 0иВ = 0и равно - 9)и; максимальное время выполнения будет достигнуто при Л = Л-1иВ=() и равно (4.5iV + 2.5N - 6)и.

5. Искомая производящая функция равна произведению z°~ и производящей функции для величины 9В - ЗА. Рассмотрев, как в предыдущем упражнении, таблицу инверсий и вспомнив, что отдельные элементы таблицы инверсий не зависят один от другого, находим искомую производящую функцию г-э ]1<<;у((1 + + г-"* -1- 2~)/j). Дисперсия равна 2.25N + 3.375N - 32.625ЛГ -1- 36Hn - 9Hff\

6. Организуйте область вывода как циклический список, в котором позиция Л будет соседней по отношению к позиции 1. Следующий элемент, который нужно вставить, берется с левого или правого конца текущей серии нерассортированных элементов в зависимости от того, оказался ли предыдущий вставленный элемент соответственно справа или слева от центра области рассортированных элементов. В конце обычно требуется "прокрутить" эту область, переместив каждую запись на к позиций по кругу, где к - некоторое фиксированное значение. Это можно эффективно выполнить способом, аналогичным рассмотренному в упр. 1.3.3-34.

7. Среднее значение для oj - j\ равно

суммируя по j, получим act) + ("з)) = К" - !)•

8. Нет; рассмотрите, например, последовательность ключей 21111111111.

9. Для табл. ЗЛ = 3-1-0-1-2-1-1 =6, 5 = 3-1-1-1-4-1-21 = 29; для табл. 4 Л = 44-2-1-24-0 = 8,5 = 44-34-84-10 = 25; следовательно, время выполнения программы D в этих двух случаях равно соответственно 786и и 734и. Хотя число перезаписей сократилось с 41 до 25, эта программа не может соперничать с программой S по времени работы, поскольку при N = 16 тратится много времени на вспомогательные операции, необходимые для организации четырех проходов. При сортировке 16 элементов лучше выполнить только два просмотра: двухпроходный вариант программы D начинает превосходить по скорости программу S примерно при Л = 13; и все же на коротких наборах входных данных они почти равноценны (а при малых значениях Л, возможно, существенную роль играет длина программы).

10. Вставить"INC1 INPUT; STl 3F(0:2)" между командами в строках 07 и 08 и заменить строки 10-17 следующими строками:

ЗН СМРА INPUT+N-H.1 NT - S JGE 8F NT - S

4Н ENT2 N-H,l NT-S-C

5Н LDX INPUT,2 В

6Н STX INPUT+H,2 В

DEC2 0.4 В

J2NP 7F В

СМРА INPUT,2 В - А

JL 5В В-А

7Н STA INPUT+H,2 NT-S-C

За счет увеличения программы на четыре команды удается сэкономить 3(С -Г) машинных циклов, где С - число случаев, когда Kj > Kj-h- В табл. 3 и 4 экономия времени составляет соответственно около 87 и 88 циклов; эмпирически значение С/{NT - S) можно выбрать равным приблизительно 0.4, если hs+i/hs « 2 и приблизительно О.З, если hs+\/hs к З, так что это усовершенствование стоит затраченных усилий. (С другой стороны, аналогичное изменение программы S нежелательно, так как экономия в этом случае пропорциональна всего лишь log N, если только заранее неизвестно, что входные данные достаточно хорошо упорядочены.)

12. Замена символом всегда приводит к изменению количества инверсий на ±1 в зависимости от того, где выполнена замена - над или под диагональю.

13. Припишите вес г - j\ сегменту от {г, j-1) до (г, j).

14. (а) Поменяйте местами г и j в сумме для Л2„ и сложите эти две суммы. (Ь) Взяв половину данного результата, видим, что

Л2.= Ео-)г0(""">1:ч)(""?)

оЫ V г А n-j у V г У V п-г-к )

следовательно, Y. nz" = Y!,k>o Ь*а7(1 - 4) = z/{l - 4г) где а = (1 - /1 - 4г )/2z.

Это доказательство сообщил автору Леонард Карлиц (Leonard Carlitz). Еще одно доказательство может основываться на взаимосвязи между весами для горизонтальных и вертикальных серий (см. упр. 13). Другой вариант доказательства можно сформулировать при помощи тождества, которое рассмотрено в ответе к упр. 5.2.2-16 при f{k) = к; однако непонятно, как, используя комбинаторику, просто вывести формулу А„ = [ri/2j2"".

15. При п > О

gn{z) = z"gn-i; hn{z) - gn{z) + 2"" gn{z);

9niz) = Zgk{z)gn-k{z)\ hn{z) =

k=l fc=l

Полагая G{w,z) = Yin > находим, что wzG{w,z)G{wz,z) = G{w,z) - 1. Из этого

представления можно вывести, что, если t = у/1 - 4w = 1 - 2w - 2w - 4w - , имее.м G{w, 1) = {l-t)/{2w); G,{w, 1) = l/{wt)-{l-t)/{2w); G{w, 1) = l/{2t)-l/{2t)- G„{w, 1) = 2/{wt) - 2/{wh) -b (1 - t)/w; G:{w, 1) = 2/t - 1/t; G"{w, 1) = 1/t - (1 - 2w)/t + lOwt Здесь нижние штрихи обозначают дифференцирование по первому параметру, а верхние - по второму параметру. Аналогично из формулы

w[zG{wz, z) + G{w, z))H{w, z) = H{w, z) - 1