Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 66
Текст из файла (страница 66)
62. (49] Определите наибольшее (ч', для которого существует совершенный сортировщик с т головкэыи. Верно ли, что Х = О(пь~)? 63. (2Я] (В. Пратт (Ч. Ргаы).) Если каждая головка Ьъ находятся в положении 2" 1 < Ь < т, то сколько проходов потребуется для сортировки последовательности нулей и единиц э, сэ... сэ, -ы где з = 0 тогда и только тогда, когда у являетсв степенью 2? 64.
[24] (Однороднал сорщоровка.) В дереве, представленном иа рис. 34 в разделе 5.3.1, сравнение 2: 3 выполняется в обеих ветвях уровня 1, а в каждой ветви уровня 2 выполняется сравнение 1:3, если только оно не является избыточным. В общем случае мы можем рассмотреть класс алгоритмов сортировки, однородных именно в этом смысле. Предполагая, что М = ( ) пар ((а, Ь) ] 1 < а < Ь < Аг) выстроены в последовательность (оп 51), (аэ, Ьэ),..., (аз!, Ьм ), мы можеъг последовательно выполнять те сравнения К„,,Къ„К,:Къ, ..., результат которых еще не известен. Каждая из М( расстановок пар (а, Ь) определяет алгоритм одно. родной сортировки. Идея однородной сортировки принадлежит Х. Л, Бьюсу (Н.
1.. Вепв) (УЛСМ 17 (1970), 482-495], в работе которого было предложено несколько следующих упражиепий. Для формального определения сщнороднай сортировки удобно воспользоваться теорией графов. Пусть С вЂ” ориентированный граф с вершииами (1, 2,..., Ю) и без дуг. Для 1 = 1, 2,..., М мы добавляем вуги к О следующим образом. Слвчай й В О имеется путь от а;к Ь,.
Добавить к С дугу а; -+ Ьь Случай й В С имеется путь от Ь, к а;. Добавить к С дугу Ь; -ъ а;. Случай 3. В С иет пути ии от а; к Ьп ии от Ь, к аь Сравнить К„: Къ,.; затем, если Кю < Къ,, добавить к О дугу а; -+ Ь,; если же Кю > Къ„то добавить дугу Ь; -+ аь Нас интересует, главкым образом, число сраввеиий ключей, выполняемых алгоритмом одиородной сортировки, а ие механизм, с помощью которого действительно устраняются избыточные сравиения; граф О иеобязательио строить в явном виде — здесь ои используется только для определеиия однородной сортировки.
Будем также рассматривать ограивчекнрю оонородную сортировку, при которой в указанных выше случаях 1-3 учитываются только пути длиной 2, (Алгоритм ограиячеиной сортировки может выполнять некоторые избыточные сравнения, но, как показано в упр. 65, анализ ограниченного случая выполняется несколько проще.) Докажите, что алгоритм ограиичеииой однородной сортировки совпадает с алгоритмом однородной сортировки, когда последовательность пар лексикографически упорядочена: (1, 2)(1, 3)(1, 4) ...(1, Р?)(2, 3)(2, 4) ...(2, А))) ...(31-1, Р(). Покажите, что иа самом деле оба алгоритма эквивалеитны алгоритму быстрой сортировки (алгоритм 5.2.2Я), если все ключи различим и избыточиые сравнения быстрой сортировки устранены, как в упр. 5.2.2-24.
(Не обращайте виимаиия иа порядок, в котором дейстяи- тельно выполняются сравнения при быстрой сортировке; учитывайте только то, какие пары ключей сравниваются.) 65. (М88) Для заданной, как в упр 56, кледоватезьности пар (ам 5~)... (ам, Ьм) пусть с, будет числом пар (у,!г), таких, что у < е ! и (а„Ь,), (а,Ьг), (аыЬь) образуют треугольник. а) Докажите, что среднее число сравнений, выполняемых алгоритмом ограниченной од- нородной сортировки, равно 2,м, 2?'(с; + 2).
Ь) Используйте результат (а) и упр. 64, чтобы определить среднее чигло неизбыточных сравнений, выполняемых при быстрой сортировке. с) Следующая последовательность пар ныюяна сортировкой методом слияния (но ие эквивалентна ей): (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.
(Ьуяз] Прибыстрой сортировке внаихудшем случаевыполняется (з) сравнений. Верно ли, что все алгоритмы ограниченной однородной сортировки (в смысле упр. 63) выполняют (з) сравнений в наихудюем лучке? 67. (.Щ8) (Х. Л, Бьюс (Н. 1. Веце).) Верно ли, что в алгоритме быстрой сортировки предполагается минимальное среднее число сравнений среди всех алгоритмов ограниченной однородной сортировки? 66. (л5) Докторская дисхертация Говарда Б, демута (Новего В. Оещпг)г) ьЕ! ессгогпс Х!ага Бог!!пй" (Ясаагогг! 1лцтегйгу, Остозег, 1956) была, вероятно, первой работой, в которой сколько-нибудь детально рассматривались вопросы сложности вычислений в приложениях этого класса, Демут рассмотрел несколько абстрактных моделей устройств для сортировки и нашел нижние и верхние оценки среднего и максимального времени выполнения, достижимого в каждой модели.
Простейшая его модель — циклическая нереверсивиая память" (рис. 61) — станет темой этого упражнения. Рис. 61. Устройство, для которого стратегия метода пузырька является оптимальной. Рассмотрим машину, которая сортирует Вг Из .., Ял за ряд проходов, где каждый проход состоит из следующих Х+ 1 шагов. Шаг 1. Установить Н е- Яь (г1 — внутренний регистр машины,) Шаг 1 для 1 < ! < М. Либо (!) установить К ~ е- Й, В е- Вз либо (й) установить Я; ~ е- В;, оставив )7 неизмененным.
Шаг Х+ 1. Установить гтл +- гс. Задача состоит в том, чтобы найти такой метод выбора между альтернативами (г) и (В), чтобы минимизировать число проходов, необходимых для сортировки, Докажите, что метод пузырька оптимален для втой модели. Другимн словами, покажите„что прн стратегии, которая выбирает альтернативу (з), если гб < Н„и альтернативу (Й), если гс > Вг, достигается минимальное число проходов. и будут в смущении ллетущне Сети... — гСннга пророка Исвин (19:9)е е Здесь праведен перевод цитаты из "Ветхого ЗавеЫ* на английском языке, использованный автором в оригинале настоящего вздаиия.
В каяоннческом издании "Виблиие на русском языке зтот стих звучит следующим образом: "И будут а смущении обрабатывающие лен н ткачи белых полотен". — дрим. верее. 5.4. ВНЕШНЯЯ СОРТИРОВКА Пгишло вгкмя заняться интересными задачами, возникающими в том случае. когда записей больше., чем может поместиться в быстродействующую оперативную память. Внешняя сортировка в корне отличается от внутренней (хотя в обоих случаях необходимо расположить записи данного файла в порядке неубывания), и объясняется это тем, что время доступа к массиву на внешних носителях жестко ограничено. Структура данных должна быть такой, чтобы сравнительно медленные периферийные запоминающие устройства (на магнитных лентах, дисках, барабанах и т. д.) могли удовлетворить потребности алгоритма сортировки.
Поэтому большинство изученных до сих пор методов внутренней сортировки (вставка, обмен, выбор) фактически бесполезно для внешней сортировки; необходимо рассмотреть всю проблему заново. Предположим. например, что предназначенный лля сортировки файл состоит из 5 000 записей В1 Вз .. Вьоааеоо длиной по 20 слов (хотя ключи В; не обязательно должны иметь такую длину). Как быть, если во внутренней памяти данной машины помещается одновременно только 1000 из этих записей? Сразу напрашивается такое решение: рассортировать каждый из пяти подфайлов В1" Вшоаюо, Взааооо1 Взоюооо, ", В4оюво1 "Вьаоаоао по отдельности и затем слить полученные подфайлы.
К счастью, слияние оперирует только очень простыми структурами данных, а именно — линейными списками, обрабатывать которые можно последовательно, как стеки или очереди. Поэтому для реализации метода слияния годятся самые непритязательные устройства внешней памяти. Только что описанный процесс — внутренняя сортировка г последующим "внешним слиянием" — весьма популярен, и наше изучение внешней сортировки сведется, в основном, к вариациям на эту тему. Возрастающие последовательности записей, получаемые на начальной фазе внутренней сортировки, в литературе о сортировке часто называются цепочками (эсг)пй).
Этот термин довольно широко распространен, ио, к сожалению, он противоречит еще более популярному термину "эФгшк" в других разделах вычислительной науки, в которых он означает произвольную последовательность символов. При изучении перестановок уже было дано вполне подходящее название для упорядоченных сегментов файла, которые мы договорнлясь называть восходящими сериями или просто сериями. В соответствии с этим будем использовать слово "серии" для обозначения упорядоченных частей файла. Таким образом, использование понятий "цепочки серий" и "серии цепочек" не приведет ни к каким недоразумениям.
Рассмотрим сначала процесс внешней сортировки, использующей в качестве вспомогательной памяти накопиглели на магниглнмх леншах (в дальнейшем для краткости будем употреблять термин "магнитные ленты"). Вероятно, простейшим и наиболее привлекательным способом слияния с помощью лент служит сбалансированное двухпртлевое слияние, в основе которого лежит иден, использовавшаяся ранее в алгоритмах 5.2.4, Х, Б и 1.
В процессе слияния нам потребуются четыре "рабочие ленты". На первой фазе восходящие серии, получаемые при внутренней сортировке, помещаются поочередно на ленты 1 и 2 до тех пор, пока не исчерпаются исходные данные. Затем ленты 1 и 2 перематываем к началу и выполняем слияние серий, которые находятся на этих лентах, получая новые серии, вдвое дэиннее исходных. Эти новые серии записываются по мере их формирования попеременно на ленты 3 и 4. (Если на ленте 1 на одну серию больше, чем на ленте 2, то предполагается, что лента 2 содержит дополнительную "фиктивную" серию длиной 0.) Затем все ленты перематываются к началу и содержимое лент 3 и 4 сливается в серии удвоенной длины, записываемые поочередно на ленты 1 и 2. Процесс продолжается (при этом длина серий каждый раз удваивается) до тех пор, пока не останется одна серия (а именно — весь упорядоченный файл).
Если после внутренней сортировки было получено 8 серий, причем 2" ~ < Я < 2", то процедура сбалансированного двухпутевого слияния произведет ровно Й = (13 Я) проходов по всем данным. Например, в рассмотренной выше ситуации, когда требуется упорядочить 5 млн записей, а объеьз внутренней памяти составляет 1 млн записей, мы имеем 8 = 5. На начальной распределительной фазе процесса сортировки пять серий будут помещены на ленты следующим образом: Вз Вювюоо' Взоаюо~ Взоооооо' Взоеюоз .
Взоооооо Внюовп -. Взвюооо' Взооовп Взеюооо (Пустая) (Пустая) Лента 1 Лента 2 Лента 3 Лента 4 После первого прохода слияния на лентах 3 и 4 получатся более длинные серии, чем на лентах 1 и 2: Вз ° " Взоооооо' Ваюови ° Взоооооо Взоооооз " Взовхюо Лента 3 Лента 4 (2) Лента 1 В~ Взоооооо (3) Лента 2 Ваюоооз " . Взоооооо (Серия Взоооооз, . Взооовю снова копиРУетсЯ, но если бы мы начали с 8 млн записей, в этот момент на ленте 2 содержалось бы Взовхюз " Взоооооо.) Например, после еще одной перемотки на ленте 3 окажется серия Вз . Взоооооо и сортировка закончится.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
