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