образом, показать, что {5, 6, 7} также попадают на свои места. Наконец, то, что {8,..., 23} должны сортироваться, следует из рассуждений, приведенных в упр. 59.

63. Если г < m - 2, то головки преобразуют цепочку 0P101*010 ... Ol-Ol в цепочку 0P"•"101*0l0.. .Ol*"" ~01~+; следовательно, необходимо т-2 проходов. [Для случая, когда головки находятся в позициях 1, 2, 3, 5,..., 1 -- 2"", Пратт получил аналогичный результат: цепочка 0Г012-012""0... И-О!, 1 < а < 2*" превращается в QP+i-a-iQ2-iQ2+i-iQ Qii"" -ioi2+9; значит, ДЛЯ такой последовательности головок в наихудшем случае требуется не менее т - [logj m] - 1 проходов. Эта последовательность головок особенно интересна, поскольку она была использована как основа весьма остроумного сортирующего устройства, изобретенного Ф. Н. Армстронгом (Р. N. Armstrong) [см. и. S. Patent 3399383 (1965)]. Пратт предполагает, что эти исходные последовательности представляют наихудший случай из возможных.]

64. При быстрой сортировке каждый ключ К2, , Км сравнивается с К\\ пусть А = {г Ki < Ki}, В = {] \ Kj > Ki}. Далее метод быстрой сортировки независимо применяется к А а В. Все сравнения Ki -.Kj для г в А и j в В запрещаются как при быстрой сортировке, так и в алгоритме ограниченной однородной сортировки, но никакие другие сравнения не запрещаются в алгоритме неограниченной однородной сортировки.

В этом случае мы могли бы еще больше ограничить алгоритм, опуская случаи 1 и 2 так, что к G добавляются дуги, только если явно выполняются сравнения, и рассматривая при проверке избыточности лишь пути длиной 2. Другой способ решения этой задачи заключается в том, чтобы рассмотреть эквивалентный алгоритм вставки в дерево (раздел 6.2.2), который выполняет те же сравнения, что и однородный алгоритм, и в том же порядке.

65. Вероятность того, что Kat сравнивается с Кь-, - это вероятность того, что d других заданных ключей не лежат между Ка и Кь; это, в свою очередь, есть вероятность того, что два числа, случайно выбранные из {1, 2,... ,с;--2}, окажутся последовательными, а именно

(с...,/("Г)-

(b) Первые п-1 значений d равны нулю; затем идут (п-2) единиц, (п-3) двоек и т. д.; среднее значение, следовательно, равно 2j2k=ii~k)/{k+l) = 2jj((n+l)/(A: + l)-l) =: 2(п + 1)(Я„+1-1)-2п.

(c) Раздвоенность, характерная для слияния, приводит к тому, что алгоритм ограниченной однородной сортировки совпадает с алгоритмом однородной сортировки для этой последовательности. Пары, содержащие вершину N, имеют значения с, равные соответственно 0,1,..., N-2; поэтому среднее число сравнений точно такое же, как и при быстрой сортировке.

66. Нет. Когда N = 5, никакая последовательность пар, оканчивающаяся на (1,5) (1,2) (2, 3)(3,4)(4, 5), не будет требовать 10 сравнений. [Интересная проблема для исследования: найти для любого конечного N однородный метод сортировки, наилучший из возможных в наихудшем случае.]

67. Гил Калаи (Gil Kalai) неофициально сообщил о найденном доказательстве минимальности для ограниченного случая. Он использовал метод, изложенный в его же статье в Graphs and Combinatorics 1 (1985), 65-79; однако само доказательство не опубликовано.

68. За каждый проход элемент может потерять не более одной инверсии, поэтому минимальное число проходов не может быть меньше максимального числа инверсий любого элемента исходной перестановки. При стратегии метода пузырька эта граница достигается, так как каждый проход уменьшает на единицу число инверсий каждого элемента, обладающего инверсиями (см. упр. 5.2.2-1). Мог бы потребоваться дополнительный проход, чтобы

определить, закончена ли сортировка, но формулировка этого упражнения позволяет нам не учитывать соображения такого рода.

Возможно, наше несчастье в том, что первая теорема в изучении вычислительной сложности автоматов установила "оптимальность" метода сортировки, который так плох с точки зрения его программной реализации! Положение аналогично истории с датчиками случайных чисел, когда было сделано несколько шагов назад, как только датчики, "оптимальные" с одной частной точки зрения, были рекомендованы для общего использования. (См. комментарии к выражению 3.3.3-(39).) Отсюда мораль: рассуждения об оптимальности зачастую сильно зависят от принятого уровня абстракции модели; всякие результаты, даже очень интересные, требуют осмотрительности при их практическом применении.

[Демут далее рассмотрел более общую машину с г регистрами (это ускоряет работу в г раз) и устройство, аналогичное машине Тьюринга, в котором направление движения может по желанию переключаться. Он обнаружил, что этот вид машин способен выполнять простые вставки и шейкер-сортировку; но любая такая машина с одним регистром должна в среднем совершить не менее (Л - Л) шагов, так как каждый шаг уменьшает общее число инверсий не более чем на единицу. Наконец, он рассмотрел г-регистровые машины с произвольным доступом и вопрос сортировки с минимальным числом сравнений. Эта часть его тезисов была опубликована в IEEE Transactions С-34 (1985), 296-310.]

РАЗДЕЛ 5.4

1. Можно обойтись без фазы внутренней сортировки, но при этом работа значительно замедлится, так как возрастет число считываний каждой части данных из внешней памяти и записи в нее.

2. Серии распределяются как в (1), затем на ленту 3 записываются Ri ... л2000000; л2000001 ... Л4000000; Л4000001 ... Д5000000. После перемотки всех лент в результате выполнения "од-нопутевого" слияния на ленты Ti и г2 будет помещено соответственно содержимое Гз и Г4 в (2). Затем Ti и г2 сливаются на Гз, информация копируется и сливается еще раз; в итоге имеем пять проходов. В общем случае эта процедура аналогична четырехленточному сбалансированному слиянию, но выполняется копирование между любыми двумя слияниями, что приводит, таким образом, к удвоенному числу проходов минус один.

3. (а) [logpS]. (b) loggS, где В = \/Р{Т - Р) - так называемая "эффективная мощность слияния". При Г = 2Р эффективная мощность равна Р, при Г = 2Р - 1 она равна Р{Р - 1) = Р - 5 - Р~ + 0(Р~), что несколько меньше, чем 5Г.

4. jT. Если Г нечетно, а Р должно быть целым, то как [Г/2], так и [Г/2] дают одинаковое максимальное значение. В соответствии с упр. 3 лучше иметь Р > Г - Р, поэтому для сбалансированного слияния мы выбираем Р = [Г/2].

РАЗДЕЛ 5.4.1

503 оо .908 оо

5оз{;

1. 087 154 170 426

Ь2б/426 653 оо

1б12 оо

2. Путь [Ш1--ЧЩ)-Н87)-{154)--{061) был заменен путем [Щ--(бТ2)--<512>--<154>--(587). (По существу, мы выполняем сортировку методом пузырька от нижней части к вершине дерева вдоль этого пути.)

3. and fourscore our seven years/ ago brought fathers forth on this/

a conceived continent in liberty nation new the to/ emd dedicated men proposition that/ all are created equal.

4. (Эта задача несколько двусмысленна; здесь мы не очищаем внутреннюю память, пока дополнительный буфер не будет близок к переполнению.)

and fourscore on our seven this years/ ago brought continent fathers forth in liberty nation new to/ a and conceived dedicated men proposition that the/ all are created equal.

5. Неверно: полное двоичное дерево с Р узлами определено для всех Р > 1.

6. Вставить "если Т = LOC(X[0]), то переход к шагу R2; в противном случае" в начало шага R6 и исключить ангьлогичную фразу из шага R7.

7. Алгоритм ничего не выдает, RMAX остается равным 0.

8. Если бы любой из первых Р регьльных ключей оказался равным оо, то запись пропала бы. Чтобы избежать этого, мы можем ввести переключатель, установив его так, чтобы на шаге R4 сравнение с LASTKEY первоначально не выполнялось. Затем, когда впервые окажется RQ О на шаге R3, переключатель изменяет свое состояние таким образом, что далее не выполняются шаг R1 и анализ RQ на шаге R3.

9. Предположим, например, что текущая серия - восходящая, тогда как следующая должна быть нисходящей. В этом случае гьлгоритм R будет работать правильно при одном изменении: на шаге R6, если RN(T) = RQ > RC, следует изменить на противоположный знак сравнения KEY(LOSER(T)) cKEY(Q).

Когда RC меняется, проверки ключей на шагах R4 и R6 должны изменяться соответствующим образом.

10. Пусть j = LQC{X[j]). Алгоритм R обеспечивает выполнение следующих условий при достижении шага R3, если заранее установлено LOSER(O) Q и RN(0) RQ. Значения LOSER(O), LOSER((P - 1)) представляют собой перестановку множества {О, 1,

(Р- 1)}; существует перестановка указателей {LOSERCj) RN(j) = 0}, которая соответствует текущей турнирной сетке. Другими словами, если RN(-j) равно нулю, величина KEY(LOSER(-j)) не имеет значения; можно переставить "проигравших" друг с другом. После Р шагов все RN( будут отличны от нуля. Таким образом, дерево будет сформировано полностью. (Ответ на указание - "да".)

Любители строгости формулировок могут возразить, что алгоритм сравнивает значения KEY, которые еще не инициализированы. Если вас это тоже смущает, можете избежать такой ситуации, установив на шаге R1 все KEY равными 0.

11. Верно. (Оба ключа принадлежат одной подпоследовательности из доказательства теоремы К.)

13. После завершения первой серии в памяти обычно остаются ключи, меньшие среднего, так как именно из-за своей малой величины они не попали в первую серию. Поэтому во вторую серию выводится большее количество меньших ключей.

14. Предположим, что снег внезапно прекращается, когда снегоочиститель находится в случайной точке и, Ч < и < 1 (после достижения установившегося состояния). Тогда предпоследняя серия содержит (l--2u-u2)P записей, а последняя - иР. Интегрирование по du дает среднее количество записей (2 - )Р в предпоследней серии и Р - в последней.

15. Неверно. Последняя серия может быть сколь угодно длинной, но только в сравнительно редком случае, когда в момент исчерпания исходных данных все записи в памяти принадлежат одной серии.

16. Тогда и только тогда, когда каждый элемент имеет меньше Р инверсий. (См. разделы 5.1.1 и 5.4.8.) Рассматривая таблицу инверсий, находим вероятность, которая равна 1 при N < Р и P~P!/iV! при N > Р. (Практически, однако, сортировка за один проход - не такое уж редкое явление, поскольку люди часто в целях предосторожности склонны сортировать файл при малейшем подозрении, что порядок в нем нарушен.)