Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 65
Текст из файла (страница 65)
[Мйб[ (Р. Л. Грэхем (Н. 1. Сгайага).) Компаратор [1:у] называется избыточным в сети а! [1:2)а«, если либо (ха!); < (ха!), для всех векторов х„либо (ха!), > (ха!)1 лля всех векторов х, Докажите, что ес.ти а является сетью с г неизбыточными компараторами, то найдется по крайней мере г различных упорядоченных пар (1,3) различных индексов, таких, что (ха), < (хп)1 для всех векторов х. (Следовательно, сеть без избыточных компараторов содержит не более (") модулей.) Рис.
00. Семейство сетей, возможность которых выполнять сортировку очень сложно проверить. Показан вариант при ги = 3 н и = 5 (см. упр. 52). ь 52. [УО] (М. О. Рабин (М. О, ВаЬьп), 1080.) Докажите, что в общем случае исключи- тельно трудно дать заключение, является ли данная последовательность компараторов сетью сортировки, анализируя сеть, аналогичную представленной на рис.
60. Принято перенумеровывать входы хо до хл, где «Ч = 2щи + из+ 2и; положительные целые числа являютгя параметрами. Первые компараторы — [у;у + 2и)6] при 1 < у < 2и и 1 < й < иг. Тогда имеем [21'-1: 2А[0121] при 1 < у < и параллельно со специальной подсетью, которая использует только индексы > 2и. Далее сравниваем [О:2пьи+2и+у] при 1 < у < пь. И наконец, существует законченная сеть сортировки для (хг,...,хл), за которой следует [О:1][1:2]...
[Х вЂ” 1 — 1;)Ч вЂ” 1], где( = пзи+ и+ 1, а) Опишите все входы (яо, хг,..., хл), которые не сортируются такой сетью, в терминах поведения специыгьной подсети, Ь) Задав множество выражений наподобие (рг Ч рг Ч рз) Л (рг Ч рз Ч р«) д, объясните, как построить специальную подсеть по типу сети, показанной на рис. 60, которая сортировала бы все входы тогда и толъко тогда, когда выражение не удовлетворяется. 58. [ЗО] (Периодическая еешь сорглироеки.) Две показанные ниже сети следует считать иллюстрацией рекурсивного построения Ьуровневой сети при и = 2' в случае 1 = 4. Если пронумеровать линии входов от 0 до 2' — 1, то 1-й уровень в случае (а) имеет компараторы [1:я, где 1 мог) 21 ы ' < 2' ' и у = 19(21+1 ' — 1); всего существует 12' ' компараторов, как и в сети битонного слияния.
В случае (Ь) компараторы первого уровня суть [22:21 + 1] при 0 <,у < 2' ' и 1-уровневые компараторы п и 2 < 1 < г суть [22+ 1: 22+ 2'+' '] при 0 < у < 2' ' — 2' ', всего имеется (Г - 1) 2' ' + 1 компараторов, как в сети четно-нечетного слияния.
Докаягите, что если входные числа 2"-упорядочены, как в теореме 5.2.1Н при некотором й > 1, то обе сети приведут к выходу, который будет 22" '-упорядочен. Таким образом, мы сможем сортировать 2' чисел, пропуская их через любую из сетей Г раз. [Когда(велико, такие сети сортировки выппоняют примерно вдвое болыпе сравнений, чем алгоритм 5,2.2М; но общая временная задержка та же, что и на рис. 57, а реализапня выполняется проще, поскольку та же самая сеть используется многократно.] о 1 2 3 4 з в г в 9 1О 11 12 ы 14 16 16 !г 13 19 го 21 22 гв 24 23 26 22 26 зв 36 зг з2 «О 41 42 «3 6 1З 14 1Ь 11 1В 19 29 2) м а вг зз 34 зь [6 зз 39 49 41 «г (а) 54, [Дй) Проанализируйте оюйства сетей сортировки, построенных не из 2-элементных сортировщиков, а из пз-сортирующих модулей, (Например, Дж.
Шапиро (С. Ягар(го) построил сеть для сортировки 16 элементов, использовав четырнадцать 4-элементных сортировщиков. Наилучшее ли это решеииеу Докажите, что тп~ элементов можно рассортировать с помощью не более 16 уровней т-элементных сортировщиков, если пэ достаточно велико.) 55. [йу) )уересшаноеа 4най сспп ю называется последовательность модулей [гыу4)... [4,:у,[, где каждый модуль [4; у[ может устанавливаться извне в одно из двух состояний; либо он передает свои входы без изменений, либо меняет местами х, и х, (независимо от значений х, и х ).
Погледовательность модулей должна быть такой, чтобы на выходе можно было получить любую перестановку входов при соответствующей установке модулей. Любая сеть сортировки является, очевидно, перестановочной сетью, но обратное неверно. Найдите перестановачиую сеть дли пяти элементов, имеющую только восемь модулей. ь 56. [25[ Предположим, что битовый вектор х б В„ие рассортирован. Покажите, что существует стандартная и-сеть а„которая не сможет рассортировать х, хотя она и сортирует другие элементы 1.1„.
57. [Муб) Чагино-нечетное слияние аналогично четно-четному слиянию Бэтчера„но, ес- ЛИ ГЛП ) 2, П)ЮЦЕСС рвхуренаиа СЛИВавт ПОСЛЕдаиатЕЛЬНОСтв (Х незь4,Хн-Э,Х,-4) (Р1 РЗ~ »,РЗ(н/21-4) И (Х( ~4нмвеэ44 °, „Хл-Ывт) С (Р2,У4,...,РЩ„ГЭ)) ПРЕжлв, ЧЕМ будет сформировано множество [т/2) + [и/2) — ! сравнений-обменов, аналогичных (1).
Покажите, что при четно-нечетном слиянии достигается оптимальное для битанного слияния время задержки [16(т+ и)), поскольку не делается сравнений больше, чем в методе битоннаго слияния. 4рактически нужно доказать, что числа сравнений А(гл, и), выполняемых при четка-нечетном слиянии, удовлетворяет условию с(пв,п) Н А(гп,п) с х(гл+ и) (бщ(п(яэ, и) + т+ эп.
УПРАЖНЕНИЯ (часть 2) Следующие упражнения ямеют отношение к различным аспектам оптимизации, касающимся сортировки. Несколько первых упражнений основаны на интересном "многоголовачнам" обобщении метода пузырька, предложенном Ф. Н. Армстронгом (Р. 58 Агшщговй) и Р, Дж, Нельсоном (В. Л. г!е!эзп) еще в 19а4 году. ]См. (7.3. Равелю 3029413, 3034102.] Пусть 1 = Ь1 < Ьз « Ь = и — возрастающая последовательность целых чисел; будем называть ее последовательностью голов длиной т с диапазоном и. Она будет использоваться при определении методов сортировки специального вида. Сортировка записей В|, Вя осуществляется за несколько проходов, а каждый проход состоит нз А!+ и — 1 шагов.
Нв шаге у прн у = 1 — и, 2 — я, ..., Ь! — 1 рассматриваются записи В +врр Ву+вр1,, .., В!+в! ! и в случае необходимости переставляются так, чтобы их ключи оказались упорядоченными. (Мы говорим, что Взяв!Н,...,Вгьь! ! находятся "под головками чтения/записи". Если у+ Ь]Ь] либо < 1, либо > Х, то запись В~+в!в! не рассматривается. Иначе говоря, ключи Ка,К-мК-з,... считаются равными -аа, а Кл+и Кя+з,... счнтаютси равными +аа. Поэтому при у < -Ь]т — 1] нли у' > Ю вЂ” Ь]2] шаг у становится тривиальным.) Например, ниже показан цкнн проход сортировки при т = 3, Ю ы 9 и Ь1 ы 1, Ьз = 2, Ьв=4 К з К1 Кв Ква Кп К1з Если т = 2, Ь| = 1 н Ьз = 2, этот "многоголовочный" метод сводится к методу пузырька (алгоритм 5,2.2В). $$, ]$1] (Джеймс Дугунджи (Лешев Х>пбппб)!).) Дозшжите, что если Ь]Ь+1] = Ь]Ь]+1 при некотором й, 1 < Ь < т, то миогогаловочный сортировщик, описанный выше, рассортирует любой входной файл за конечное чясло проходов, Но если Ь]Ь+ 1] > Ь]Ь]+ 2 при 1 < Ь < т, то не исключен вариант, когда вкодная последовательность никогда не будет упорядочена.
ь $9. ]30] (Армстронг (Аппвсгопб) и Нельсон (г!е!вопЦ Пусть Ь]Ь+ 1] < Ь[Ь]+ Ь при 1 < Ь < т и М > и-1. Докажите, что в течение первого прохода наибольшие п — 1 элементов всегда займут свои окончательные места. ]Указание. Используйте принцип нулей и единиц; докажите, что если сортируется последовательность нз нулей и единиц, причем единиц меньше и, то все головки могут читать едииищя лишь в том случае, когда все нули лежат слева от головок,] Докажите, что если головки удовлетворяют сформулированным условиям, то сортировка будет закончена не более чем за ](М вЂ” 1)7'(я — 1)] проходов.
Существует ли входной файл, для которого необходимо так много проходов? 60. ]$6] Докажите, что, если я ~ Ь7, при первом проходе наименьший ключ будет помещен в позншпо Вв тогда и только тогда, когда Ь]Ь+ 1] < 2Ь]Ь] прн 1 < Ь < т. 2=-3 7=-2 у = -1 у =0 7=1 у=2 2=3 у -5 1=6 2=7 7=8 Ка К1 Кз 3 1 3 1 3 1 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 КЗ К4 4 5 4 5 4 5 4 5 4 5 2 4 2 4 2 4 2 4 2 4 2 4 2 4 Кв Кв 9 2 9 2 9 2 9 2 9 2 9 5 6 Т 5 6 Т 6 5 6 5 6 5 6 Кг Кв 6 8 6 8 6 8 6 8 6 8 6 8 9 8 9 8 7 8 7 8 7 8 7 8 7 7 7 7 7 7 7 7 9 9 9 9 61. (34] (Дж.
Хопкрофт (3. Норсгой),) "Совершенным сортирошпиком" й( элементов иа.- зывается многоголовочиый сортировщик, который всегда заканчиваиг работу за один проход. В упр. 59 доказана, что последовательность (Ьпйюйэ,йм...,й ) = (1,2,4,7,,1+ ( )) образует совершенный сортировщик лля Ю = ( ) + 1 элемеитов, используя гл = (~/8У вЂ” 7+ 1)/2 головок. Напркмер, последовательиостыоловок (1, 2, 4, 7, 11, 16, 22) является совершенным сортировщиком для 22 элементов. Докажите, что последовательность головок (1, 2,4, 7, 11, 16, 23) иа самом деле будет совершенным сортировщиком для 23 элементов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
