Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 60
Текст из файла (страница 60)
е. выполнять их параллельно (если в нашем распоряжении имеется компьютер с соответствующей архитектурой). Например, пять шагов на рис, 43 и 44 сокращаются до трех, если организовать одновременные неперекрывающиеся операции сравнения, так как можно объединить первые два и следующие два шага. Ниже в данном разделе мы используем это свойство сетей сортировки. Таким образом, сети сортировки могут оказаться очень полезными на практике, хотя возможность построения эффективной сети сортировки и элементов при больших и вовсе не очевидна; возможно, мы обнаружим, что для поддержания однородной структуры решений требуется много дополнительных сравнений.
Если дана сеть для и элементов, имеется два простых способа построения сети сортировки для и + 1 элементов: один — с использованием принципа всшоекн, а другой — принципа выбора. На рис. 45, (а) показано, как (и + 1)-й элемент может быть вставлен на нужное место после того, как первые и элементов рассортированы, а на рис.
45,(Ь) показано, как можно выбрать наиболыпий элемент, прежде чем перейти к сортировке остальных элементов. Многократное применение процедуры, показанной на рис. 45, (а), позволяет получить сетевой аналог метода простых вставок (алгорнтм 5.2.15), а многократное применение процедуры на рис. 45,(Ь) приводит к сетевому аналогу метода пузырька (алгоритм 5.2.2В).
Рис. 46. Оетевые аналоги элементарных схем внутренней сортировки, которые получены в результате многократного применения операции, представленной на рис. 45: (а) простая вставка,(Ь) метод пузырька. На рис. 45 изображены соответствуюп1ие сети для шести элементов. Интересно заметить, что если сжать каждую сеть, чтобы обеспечить выполнение одновременных операций, то оба метода сведутся к одной и той же "треугольной" процедуре с (2п — 3) стадиями (рис. 47).
Рис. 47. При параллельном выполнении операций метод простой вставки совпадает с методом пузырька.'„ Легка доказать, что сети, представленные на рис. 43 и 44, позволяют сортировать любое множество из четырех чисел, поскольку первые четыре комцаратора направляют наименьший и наибольший элементы на положенные им места, а последний компаратор располагает в требуемом порядке остальные два элемента, Однако не всегда так легко сказать, будет ли данная сеть сортировать все возможные входные носледоватальности; например, сети являютсл правильными четырехэлементными сетями сортировки, но доказательство их правильности отнюдь не тривиально. Конечно, для этого достаточно проверить каждую и-элементную сеть на всех и! перестановках и различных чисел, но фактически мы можем обойтись значительно меньшим количеством проверок.
Теорема Е (Принцип нулей и единиц). Если сеть с и входами сортирует в порядке неубывания все 2" погдедопагелыюпгей лз О и 1, то опа будет сортировать в том же порядке любую последовательность и чисел. Доказагпельстоо. (Это частный случай теоремы Бурнсиуса (ВопНсшз); см. упр. 5.3.1 12.) Если /(х) — любая монотонная функция, для которой /(х) < /(у) при х < у, и если данная сеть преобразует (хы..., х„) в (уы..., у„), то, как нетрудно видеть, эта сеть преобразует (/(хз),..., /(х„)) в (/(у1),..., У(у„)). Если у; > узы при некотором з, то рассмотрим монотонную функцию /, которая для всех чисел < у; принимает значение О, а для всех чисел > у; — значение 1. Эта функция определяет последовательность нулей и единиц (/(хз),, .., /(х„)), которая не сортируется данной сетью.
Значит, если все последовательности 0-1 поддаются сортировке, то будем иметь у; < у;~г для всех 1 < 1 < и. Принцип нулей и единиц довольно полезен для построения сетей сортировки. В качестве нетривиальвого примера можно с его помощью вывести обобщенный вариант "'обменной сортировки со слиянием" Бэтчера (влгоритм О.2.2М).
Идея состоит в том, чтобы сортировать т+ и элементов, сортируя первые т и последние и элементов независимо, а затем "пропустить' результат через (т, и)-сеть слияния. Построить (т, и)-сеть слияния можно по индукции следующим образом. а) Если т = О или и = О, то сеть пуста. Если зи = и = 1, то сеть состоит из единственного модуля компаратора. Ь) Если ти > 1, обозначим сливаемые последовательности через (хы..., х ) и (уы.,.,у„).
Сольем "нечетные последовательности" (хи хз,..., хэви„,~з1,) и (уы уз, ...,уз(„7з) з) и получим рассортированный результат (вы из,..., о~ 7з~+~„~з1); сольем четные последовательности (хз,хм...,хз(„,д)) и (уз,у4, уз( 7з1) н полу чнм рассортированный результат (юыюз,...,юр„,уз,~~„7з~). И наконец, применим операции сравнения-обмена юг из~ юз ° оз~ юз ею ." 1 юртуз)+(п/з) гц к последовательности (пыюыоз,юз,ез,юз,...,е( уз~+у„уз),ю~,7з~~.(„узри*,и* ). (2) Теперь результат будет рассортировав.
()) Здесь о' = о(„,~з.+~„~з1 г не существует, если т и и оба четные, и о" = пр„,уз~ы.р„уз)ч.з существует., лишь если т и и оба не зетные; общее число модулей ком параторов, указанных в (1), равно ((т+и — 1) /2) . Назовем (т,и)-сеть слияния Бэтчера четно-нечетным слплннам. Построенное в соответствии с этими принципами (4, 7)-слияние показано на рис. 48. Чтобы доказать, что эта довольно странная процедура действительно работает при ти > 1, воспользуемся принципом нулей и единиц и проверим ее на всех последовательностях 0 и 1. После начальных сортировок т и и последовательность (хз,.,.,х ) будет состоять из к нулей, за которыми следуют ги — Й единиц, а последовательность (уы..., у ) — из 1 нулей с послелующими и — 1 единицами при некоторых Й и 1.
Значит, последовательность (вы ею... ) будет состоять из точно ) к/21 + (1/21 нулей с последующими единицами, а (юнтао.... ) — из 1к/2) + (1/21 Х! Х2 Хз Х! У! У2 Уз У! ээ Уб Уг 22 22 Х! 22 Ха 27 22 22 2!О 22! 8, а й 8 а е Рис. 46. Четно.нечетное слияние для ш ~ 4 и н = 7. нулей с последующими единицами. Решающим моментом доказательства является то, что мы можем вывести соотношение С(пт+ 1, и+ 1) — С(7п, и) = (28т) + 2+ 1п/2"э~1+'), если и > п2 > 1.
(5) Следовательно, С(7п,пт+ г) = В(т) + щ+ В (г) нри пт > О и г > О, (6) где В(п2) = ~™, (18 Ц вЂ” это функция "бинарной вставки" из соотношения 5.3.1- (3), а В„,(г) обозначает сумму первых пт членов ряда ~ — ~ + ~ — ~ + ~ — ~ + ~ — ~ + ~ — ( + .. + ~ —,) +... (7) Если же г = О, получаем важный частный случай С(т, 7п) = В(п2) + 2п. (8) Кроме того, если 1 = (!87п), то 22 (с+2!) В (г)+1 2! 2+2 2! 2+...+2! ! 2е+7п =И ()+ +1 2'-'. ((72/2) + (1/21) — (((2/2) + (1/2)) = О, 1 или 2. (3) Если эта разность равна О или 1, то последовательность (2) уже упорядочена, а если она равна 2, то одна из операций сравнения-обмена в (1) ставит все на свои места.
Доказательство завершено. (Заметим, что принцип нулей и единиц сводит (™ ") случаев в задаче слияния всего лишь к (и!+ 1)(п + 1) случаям, каждый из котор!ых представляется двумя параметрами — Й и 1,) Пусть С(т, и) — число модулей компараторов, используемых прн четно-нечет- ном слиянии ш- н п-элементов, не считая начальных т- и п-сортировок: имеем ~ 7ПП, если глп < 1; С(, )=1 $ С((7п/2) (и/21)+С((пт/2), 1п/2))+ ((от+и — Ц/2), если тп > 1. (4) В общем случае это не слишком простая функция от 7п н и! однако, заметив., что С(1, п) = п и что С(и!+1,п+1) -С(т,п) = 1+ С(17п/2) + 1, 1н/2) Е 1) — С(1т/2), 1п/2)), если 7пп > 1, Следовательно, С(т, и + 2') — С(ш, и) имеет простой вид и г! т1 С(ш,п) = ~-+ — 7! и+ 0(1) при фиксированном т, п -> оо, ! = ~)йт); (9) 2>) член 0(1) становится, в конце концов, периодической функцией от п с периодом 2'.
Асимптотически при и -> оо величина С(п, и) = п (и и + 0(п), как следует из (8) и упр. о.3.1-1о. Сети с минимальным числом сравнений. Пусть Я(п) — минимальное число сравнений, требуемых в сети сортировки для и элементов; ясно, что Я(п) > 5(п), где Я(п) — минимальное число сравнений, необходимое для сортировки безо всяких ограничений (см. раздел 5.3.1). Мы видели, что Я(4) = 5 = Б(4), поэтому новое ограничение не приведет к потере эффективности при и = 4; но уже при и = 5 оказывается, что 5(5) = 9, в то время как Я(5) = 7. Задача определения Я(п) кажется еще более трудной, чем задача определения В(п); до сих пор неизвестно даже асимптотическое поведение Я(п). Интересно проследить историю поиска путей решения этой задачи, так как каждый новый шаг стоил определенных усилий.
С>ти сортировки были впервые исследованы Ф. Н. Армстронгом (Р. 5!. Агшзсгопй), Р. Дж. Нельсоном (В.. Я. Хе)зоп) и Д. Дж. О'Коннором (П. 3. О'Соппог) около 1954 года !сь>. Г Я. Рагепг 3029413!. Как сказано в их патентной заявке, "приложив старания, можно сконструировать экономичные п-входные сортирующие переключатели с помощью уменьшенного чмоав двухвходовых сортирующих переключателей". Показав, что Я(п+ !) < 5(н) + и, оии предложили специальные конструкции для 4 < и < 8, использовав соответственно 5, 9, 12, 18 и 19 компараторов.
Работая дазее над этой задачей, Нельсон совместно с Р. Ч. Бозе (Н. С. Вове) задались целью показать, что Я(2") < 3" — 2" при всех и; следовательно, о(п) =- 0(п>" з) = 0(п' ь""). Бозе и Нельсон опубликовали свой интересный метод в,У 4 СЛ! 9 (1962), 282 -296, где ь»кказали предположение, что зто наилучший возможный результат: Т. Н. Хиббард (Х. Н, Н!ЬЬаг>!) в 2АСЪХ 1Р (1963), 142-150, описал аналогичный., но более простой л>етод, в котором используется такое же число сравнений, подкрепив тем самым зто предположение. В 1964 году Р, У.
Флойд (Н. %. Р!оус!) н Д, Э. Кнут использовали новый подход к этой задаче, приведший к асимптотической оценке вида 5(п) = 0(п»'/'>М" ). Независимо К. Э. Бэтчер (К. Е. ВассЬег) разработал описанную выше общую стратегию слияния. Используя компарьтгоры, число которых определяется рекурсивным выражением с(1) = О, с(п) = с()п/2)) + с(г~п/2)) + С(~п/2), '!и/2)) при и > 2, (10) он доказал, что (см. упр. 5.2.2 — 14) с(2') = (1~ — !+ 4)2~ ~ — 1; следовательно, Я(п) = 0(п()ой п)з). Как Бзтчер, так и Флойд с Кнутом опубликовали свои конструкции ли>пь через некоторое время (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
