AOP_Tom3 (1021738), страница 17
Текст из файла (страница 17)
Любая сеть сортировки является, очевидно, перестановочной сетью, но обратное неверно. Найдите перестановочную сеть для пяти элементов, имеющую только восемь модулей. ь 55. [25) Предположим, что битовый вектор х Е 22 не рассортировав Покажите, что существует стандартная п-сеть о, которая не сможет рассортировать х, хотя она н сортирует другие элементы О„. 57. [Муу] Четно-нечетное слилние аналогично четно-четному слиянию Бэтчера, но, если топ > 2, процесс рекурсивно сливает последовательность (х„,„„згэы...,х з,х . г) с (у~ уз,. - угъ1г1-г) н (х1 ~тй и згг н,х — г,х ) с (уг, уш...,уг1„~г1) прежде, чем будет сформировано множество [т/2) + (и/2[ — 1 сравнений-обменов, аналогичных (1).
Покажите, что при четно-нечетном слиянии достигается оптимальное для битонного слияния времн задержки [1б(т+ гг)), поскольку не делается сравнений больше, чем в методе битонного слияния. Фактически нужно доказать, что число сравнений А(гл, и), выполняемых при четно-нечетном слиянии, удовлетворяет угловию С(т, и) < .4(го, и) < -'(та+ и) 15 поп(т, и) + т+ го. УПРАЖНЕНИЯ (часть 2) Следующие упражнения имеют отношение к различным аспектам оптимизации, касающимся сортировки. Несколько первых упражнений основаны на интересном "многоголовочном" обобщении метода пузырька, предложенном СР.
Н. Армстронгом (Р. Х. Аппвсгопб) и Р. Дж. Нельсоном (Н. Х. Хе!игп) еще в 1954 голу. [См. 17.5. Расепш 3029413, 3034102.[ Пусть 1 = Ьс < Ьг « . Ь„, = и — возрастающая последовательность целых чисел; будем называть ее последовательностью голов длиной сп с диапазоном и, Оиа будет использоватьсн при определении методов сортировки специального вида. Сортировка записей 11с...гссл осуществляется за несколько проходов, а каждый проход состоит из Ас + и — 1 шагов. На шаге у при у' = 1 — и, 2 — и, ..., Ас — 1 рассматриваются за~~с~ Кгзз1ср сгу+л<гр, Йг.сз1 ~ и в случае необходимости переставляются так, чтобы их ключи оказались упорядоченными.
(54ы говорим, что Кз збсср...,йзец 1 находятся "под головками чтения/записи! Если 1 + Ь[Ь) либо < 1, либо > Ас, то запись Йг+з~ь1 не рассматривается. Иначе говоря, ключи Кв,К ы К г,... считаются равнымн -оо, а Китс, Кл+г,... считаются равными +ос. Поэтому при г < -Ь[пс — Ц или г > Ас — А[2[ шаг с становится тривиальным.) Например, ниже показан один проход сортировки при пс = 3, Ас = 9 и Ьс = 1, Ьг —— 2, Аз=4 Кз Кг Кса Ксс Кш КсКеКс Если пс = 2, Ьс — — 1 и Ьг = 2, этот "многоголовачный" метод сводится к метсщу пузырька (алгоритм 5.2.2В). 58. [9Ц (Джеймс Дугунджи (Лешев Ппбппс()1) ) Докажите, что если Ь[/с+ Ц = Ь[Ь) + 1 при некотором Ь, 1 < Ь < щ, то многоголовочный сортировщик, описанный выше, рассортирует любой входной файл за конечное число проходов. Но если Ь[Ь+ Ц > Ь[Ь[+2 при 1 < Ь < пз, то не исключен вариант, когда входная последовательность никогда не будет упорядочена.
з 59. [30[ (Армстронг (Аппвсгопб) и Нельсон (Хе1воп).) Пусть Ь[/с+ Ц < Ь[Ь[+ Ь прн 1 < Й < сп и Х > и — 1. Докажите, что в течение первого прохода наибольшие и — 1 элементов всегда займут свои окончательные места. [Указание. Используйте принцип нулей и единиц, докажите, что если сортируется последовательность из нулей и единиц, причем единиц меньше и, то все головки могут читать единицы лишь в том случае, когда все нули лежат слева от головок.[ Докалсите, что если головки удовлетворяют сформулированным условиям, то сортировка будет закончена не более чем за )(Ьу — 1)/(и — 1)1 проходов. Существует ли входной файл, для которого необходимо так много проходов? 60.
[20] Докажите, что, если и = Ас, при первом проходе наименьший ключ будет помещен в позицию йс тогда и только тогда, когда Ь[Ь + Ц < 2Ь[Ь[ при 1 < lс < пз. К г — 3 — 2 -1 0 1 2 3 4 5 б 7 8 3 3 3 1 1 1 1 1 1 1 1 1 Кг Кз Кс 1 4 5 1 4 5 1 4 5 3 4 5 3 4 5 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 к к к 9 2 б 9 2 6 9 2 6 9 2 6 9 2 б 9 5 6 6 5 9 5 б 9 5 6 7 5 6 7 5 6 7 5 6 7 8 7 8 7 8 7 8 7 8 7 8 7 8 7 8 7 8 9 8 9 8 9 8 9 61. (Ц) (Дж. Хопкрофт (Л.
Норсгой),) "Совершенным сортировщиком" Ю элементов называется многоголовочный сортировщик, который всегда заканчивает работу за один проход. В упр. 59 доказано, что последовательность (6|,6а,йь,бь,...,6,~) = (1, 2,4, 7,..., 1 + (~)) образует совершенный сортировщик для 1ч' = ("') + 1 элементов, используя га = (ь/8Х вЂ” 7+ 1)/2 головок. Например, последовательность головок (1, 2, 4, 7, 11, 16, 22) является совершенным сортировщиком для 22 элементов.
Докажите, что последовательность головок (1, 2, 4, 7, 11, 1б, 23) на самом деле будет совершенным сортировщиком для 23 элементов. 62, [49) Определите наибольшее Ж, для которого существует совершенный сортировщик с ш головками. Верно ли, что Л' = 0(га )" 2 63. (93) (В. Пратт (1Ь Ргаьс) ) Если каждая головка Ьь находится в положении 2" 1 < 6 < пь, то сколько проходов потребуется для сортировки последовательности нулей и единиц гч хэ... хэ -м где ку = 0 тогда и только тогда, когда 1 является степенью 2? 64.
(94) (Однароднал соргаирввка.) В дереве, представленном на рис. 34 в разделе 5.3.1, сравнение 2: 3 выполняется в обеих ветвях уровня 1, а в каждой ветви уровня 2 выполняется сравнение 1: 3, если только оно не является избыточным. В общем случае мы можем рассмотреть класс алгоритмов сортировки, однородных именно в этом смысле. Предполагая, что М = (ь) пар ((а, Ь) ~ 1 < а < Ь < Х) выстроены в погледовательность (ам Ьь ), (аг, Ьэ),, (ам, Ьм), мы можем последовательно выполнять те сравнения Кю: Кьы Кв, ."Кь„..., результат которых еще не известен. Каждая из М! расстановок пар (а, 6) определяет алгоритм однородной сортировки.
Идея однородной сортировки принадлежит Х Л. Бьюсу (Н, Ь. Вевз) (дАСМ 17 (1970), 432-495), в работе которого было предложено несколько следующих упражнений. Для формального определения однородной сортировки удобно воспользоваться теорией графов. Пусть С вЂ” ориентированный граф с вершинами (1, 2,..., АГ) и без дуг. Для ь = 1, 2,..., М мы добавляем дуги к С следующим образом. Случай 1. В С имеется путь от а, к 6,. Добавить к С дугу а; -ь Ь,, Случай й В С имеется путь от Ь, к а,. Добавить к С дугу Ь; -+ а,. Случай й В С нет пути ни от а; к Ь„ни от Ь, к а,. Сравнить К„,: Кь,.; затем, если К,.
< Кь,, добавить к С дугу а; -+ 6п если же Кгн > Кьм то добавить дугу 6; -+ а,. Нас интересует, главным образом, число сравнений ключей, выполняемых алгоритмом однородной сортировки, а не механизм, с помощью которого действителыю устраняются избыточные сравнения: граф С необязательно строить в явном виде — здесь он используется только для определения однородной сортировки. Будем также рассматривать ограниченную вднорвднум свргаирввку, при которой в укаэанных выше случаях 1-3 учитываются только пути длиной 2.
(Алгоритм ограниченной сортировки может выполнять некоторые избыточные сравнения, но, как показано в упр. 65, анализ ограничеьпього случая выполняется несколько проще.) Докажите, что алгоритм ограниченной однородной сортировки совпадает с алгоритмом однородной сортировки, когда последовательность пар лексикографически упорядо- чена: (1, 2)( 1, 3)(1, 4) ... (1, 19)(2, 3)(2, 4) ... (2, ?У) ... ()У вЂ” 1, А ). Покажите, что на самом деле оба алгоритльа эквивалентны алгоритму быстрой сортировки (алгоритм 5.2.2Я), если все ключи различны и избыточные сравнения быстрой сортировки устранены, как в упр. 5.2.2-24.
(Не обращайте внимания на порядок, в котором действи- тельно выполняются сравнения при быстрой сортировке; учитывайте только то, какие пары ключей сравниваются.) 65. (МЯЗ) Для заданной, как в упр 58, и ~оледовательности пар (ам 5|)... (ам,бм) пусть с, будет числом пар ()й), таких, что у < л 1 и (а„Ь,), (а„Ь,), (аь,Ьь) образуют треугольник. а) Докажите, что среднее число сравнений, выполняемых алгоритмом ограниченпой од- нородной сортировки, равно 2,","л 2/(с, + 2).
Ь) Используйте результат (а) и упр. 64, чтобы определить среднее число неизбыточвых сравнений, выполняемых при быстрой сортировке. с) Следующая последовательность пар навеяна сортировкой методом слияния (но ие эквивалентна ей): (1, 2)(3, 4)(5, б) ...(1, З)(1, 4)(2, З)(2, 4)(5, 7) ...(1, 5)(1, б)(1, 7)(1, 8)(2, 5) ... Вудет ли при однородном методе, основанном на этой последовательиости, выполиятьсн в среднем больше или меньше сравнений, чем при быстрой сортировке? 66. (Мху] При быстрой сортировке в наихудшем случае выполняется ( ) сравнений. Верно ли, что все алгоритмы ограниченной однородной сортировки (в смысле упр. 63) выполняют (' ) сравпений в наихудшем случае? 67.
(М43) (Х. Л Бьюс (Н, П Вепэ).) Верно ли, что в алгоритме быстрой сортировки предполагается минимальное среднее число сравнений среди всех алгоритмов ограииченной однородпой сортировки? 68. (ь5) Докторская диссертация Говарда Б. Демута (Новагб В РешисЬ) 'Е)ессгоп1с Раса Богйпб" (Ягал1огп' 1,'п1тегэ1гу, Оссобег, 1956) была, вероятно, первой работой, в которой сколько-нибудь детально рассматривались вопросы сложности вычислений в приложениях этого класса. Демут рассмотрел несколько абстрактных моделей устройств для сортировки и нашел нижние и верхние оценки среднего и максимального времени выполнения, достижимого в каждой модели.
Простейшая его модель — — "циклическая нереверсивная память" (рис. 61) — станет темой этого упражцепия. Запв ение Рис. 61. Устройство, длк которого стратегия метода пузырька является оптимальной. Рассмотрим машину, которая сортирует й~ Яз...
Лд за ряд проходов, где каждый проход состоит из следующих?т'+ 1 шагов. Шаг 1. Установить Н е — Кь (й — внутренний регистр машины.) Шае 1 для 1 < 1 < Л. Либо (1) установить В, ~ е- И, Я е- Вц либо (и) установить Л, ~ е- гсц оставив В неизмененным. Шаг Ю+ Б Установить Ян»- тс. Задача состоит в том, чтобы найти такой метод выбора между альтернативами (з) и (й), чтобы минимизировать число проходов, необходимых для сортировки. Докажите, что метод пузырька оптимален для этой модели. Другими словами, покажите, что при стратегии, которая выбирает альтернативу (~), если Я < гс„и альтернативу (й), если Й > А„достигается минимальное число проходов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
