61. [34] (Дж. Хопкрофт (J. Hopcroft).) "Совершенным сортировщиком" N элементов называется многоголовочный сортировщик, который всегда заканчивает работу за один проход. В упр. 59 доказано, что последовательность (hi,h2, кз, Ы,..., hm) = (1, 2,4, 7,..., 1 -I-(")) образует совершенный сортировщик для N = () -I- 1 элементов, используя тп - {\/8N - 7+ 1)/2 головок. Например, последовательность головок (1,2,4, 7, И, 16, 22) является совершенным сортировщиком для 22 элементов.

Докажите, что последовательность головок (1,2,4,7,11,16,23) на самом деле будет совершенным сортировщиком для 23 элементов.

62. [49] Определите наибольшее N, для которого существует совершенный сортировщик с m головками. Верно ли, что N = О(т)?

63. [23] (В. Пратт (V. Pratt).) Если каждая головка hk находится в положении 2*~, 1 < к < тп, то сколько проходов потребуется для сортировки последовательности нулей и единиц ZiZ2 .. Z2m-i, где Zj = О тогда и только тогда, когда j является степенью 2?

64. [24] (Однородная сортировка.) В дереве, представленном на рис. 34 в разделе 5.3.1, сравнение 2:3 выполняется в обеих ветвях уровня 1, а в каждой ветви уровня 2 выполняется сравнение 1:3, если только оно не является избыточным. В общем случае мы можем рассмотреть класс алгоритмов сортировки, однородных именно в этом смысле. Предполагая, что М - () пар {{а,Ь) \ 1 < а < b < N} выстроены в последовательность

(ii, bi), (аг, 62),. •., {ам,Ьм),

мы можем последовательно выполнять те сравнения Ка.Кь,, Ка2Кь2, результат которых еще не известен. Каждая из М\ расстановок пар (а, 6) определяет алгоритм однородной сортировки. Идея однородной сортировки принадлежит X. Л. Бьюсу (Н. L. Beus) [JACM 17 (1970), 482-495], в работе которого было предложено несколько следующих упражнений.

Для формального определения однородной сортировки удобно воспользоваться теорией графов. Пусть G - ориентированный граф с вершинами {1,2,..., N} и без дуг. Для г = 1, 2,..., М мы добавляем дуги к С следующим образом.

Случай 1. В G имеется путь от aj к ftj. Добавить к G дугу Oj -¥bi.

Случай 2. В G имеется путь от 6; к aj. Добавить к G дугу 6, -» at.

Случай 3. В G нет пути ни от aj к 6,, ни от bi к ai. Сравнить Kai Кь; затем, если Kai < , добавить к G дугу т -¥bi; если же Kai > , то добавить дугу 6i Oi.

Нас интересует, главным образом, число сравнений ключей, выполняемых алгоритмом однородной сортировки, а не механизм, с помощью которого действительно устраняются избыточные сравнения; граф G необязательно строить в явном виде - здесь он используется только для определения однородной сортировки.

Будем также рассматривать ограниченную однородную сортировку, при которой в указанных выше случаях 1-3 учитываются только пути длиной 2. (Алгоритм ограниченной сортировки может выполнять некоторые избыточные сравнения, но, как показано в упр. 65, анЕшиз ограниченного случая выполняется несколько проще.)

Докажите, что алгоритм ограниченной однородной сортировки совпадает с алгоритмом однородной сортировки, когда последовательность пар лексикографически упорядочена:

(1,2)(1,3)(1,4)... (1, iV)(2,3)(2,4)... (2, iV)... (iV-1, iV).

Покажите, что на самом деле оба алгоритма эквивалентны ешгоритму быстрой сортировки (алгоритм 5.2.2Q), если все ключи различны и избыточные сравнения быстрой сортировки устранены, как в упр. 5.2.2-24. (Не обращайте внимания на порядок, в котором действи-

тельно выполняются сравнения при быстрой сортировке; учитывайте только то, какие пары ключей сравниваются.)

65. [М38] Для заданной, как в упр 5Ь, последовательности пар (ai,6i)... (ам,6м) пусть а будет числом пар {j,k), таких, что j < h " г и (а.,6i), {aj,bj), {ak,bk) образуют треугольник.

a) Докажите, что среднее число сравнений, выполняемых алгоритмом ограниченной однородной сортировки, равно Jfi 2/(ci -I- 2).

b) Используйте результат (а) и упр. 64, чтобы определить среднее число неизбыточных сравнений, выполняемых при быстрой сортировке.

c) Следующая последовательность пар навеяна сортировкой методом слияния (но не эквивалентна ей):

(1,2)(3,4)(5,6)...(1,3)(1,4)(2,3)(2,4)(5,7)...(1,5)(1,6)(1,7)(1,8)(2,5)...

Будет ли при однородном методе, основанном на этой последовательности, выполняться в среднем больше или меньше сравнений, чем при быстрой сортировке?

66. 1М29] При быстрой сортировке в наихудшем случае выполняется () сравнений. Верно ли, что все алгоритмы ограниченной однородной сортировки (в смысле упр. 63) выполняют () сравнений в наихудшем случае?

67. [М48] (X. Л. Бьюс (Н. L. Beus).) Верно ли, что в алгоритме быстрой сортировки предполагается минимальное среднее число сравнений среди всех алгоритмов ограниченной однородной сортировки?

68. [25] Докторская диссертация Говарда Б. Демута (Howard В. Demuth) "Electronic Data Sorting" (Stanford University, October, 1956) была, вероятно, первой работой, в которой сколько-нибудь детально рассматривались вопросы сложности вычислений в приложениях этого класса. Демут рассмотрел несколько абстрактных моделей устройств для сортировки и нашел нижние и верхние оценки среднего и максимального времени выполнения, достижимого в каждой модели. Простейшая его модель - "циклическая нереверсивная память" (рис. 61) - станет темой этого упражнения.

Запись

Чтение

Рис. 61. Устройство, для которого стратегия метода пузырька является оптимальной.

Рассмотрим машину, которая сортирует Ri R2 Rn за ряд проходов, где каждый проход состоит из следующих N + 1 шагов.

Шаг 1. Установить Д Дь (R - внутренний регистр машины.)

Шаг i для 1 < г < iV. Либо (i) установить <г- R, R (г- Ri, либо (ii) установить

Ri-i Ri, оставив R неизмененным.

Шаг N+l. Установить Rn <r- R.

Задача состоит в том, чтобы найти такой метод выбора между альтернативами (i) и (ii), чтобы минимизировать число проходов, необходимых для сортировки.

Докажите, что метод пузырька оптимален для этой модели. Другими словами, покажите, что при стратегии, которая выбирает альтернативу (i), если Д < iti, и альтернативу (ii), если R> Ri, достигается минимальное число проходов.

И будут в смущении плетущие сети... - Книга пророка Исайи (19:9)*

* Здесь приведен перевод цитаты из "Ветхого Завета" на английском языке, использованный автором в оригинале настоящего издания. В каноническом издании "Библии" на русском языке этот стих звучит следующим образом: "И будут в смущении обрабатывающие лен и ткачи белых полотен". - Прим. перев.