Алгоритмы - построение и анализ (1021735), страница 167
Текст из файла (страница 167)
Все эти четыре частных случая показаны на рис. 27.8. Последовательности из нулей выделены белым фоном, а последовательности из единиц — серым. Случаи, в которых точка деления пополам приходится на последовательность единип„ представлены в частях а-б, а случаи, в которых она приходится на последовательность нулей, — в частях в-а Для каждого из них лемма выполняется. и Битонический сортировщик Рекурсивно комбинируя полуфильтры, как показано на рис.
27.9, можно составить битоаический соргааровщик (Ьйоп1с зог1ег), представляющий собой сеть, юторая сортирует битонические последовательности. Первый модуль сети В1тоьлс Боктяк[п] представляет собой модуль Них Сьнлннк[п], юторый, согласно лемме 27.3, выдает две битонические последовательности половинного размера, причем каждый элемент из верхней половины не превышает по величине любой элемент из нижней половины. Таким образом, сортировку можно завершить с помощью двух юлий модуля В~тоьпс Боктнк[п/2], рекурсивно сортируюший обе половины. На рис.
27.9а рекурсия показана явно. Здесь после модуля Нльг С~.плнпк[п] расположены два модуля Нл~.г Сьплннк[п/2]. На рис. 27.96 схема представлена в развернутом виде, демонстрируя полуфильтры все меньшего размера, образующие остальную часть битоннческого сортировщика. Каждый полуфильтр выделен затененным фоном. Возле проводов приведены примеры возможных нуль-единичных значений. Глубина 23 (и) сети В~тоьпс Боктнк[п] выра- Глава 27.
Сортирующие сети 811 Соавненис разлсленис 0бзвлгнгави / т 1О( Низ Всрл Л Ы Нвз ~1' т Битоническая ~ последователи ость Бггтогггтчсскзя (" огноропнвя Бвгоническая послеповагслмгость 1 Верь Веря — Вг *'.::,~ '::;, — Лв Гтт ~ 1!„— Оа Низ последоватгзииостз т Битомгческая ) олноро.жм ггосггслгггза ге,гг гзость — э- — „-~; ) Бюоническая послезовмслигоогь Всрк Веря 1~ 3 Бюоничссьая последовательность Низ Бпаоническая О олггорггзтггзя послкзггватегьгзость зн Бгпоикческая последовательность , О ~ ~ ' ' Вср» Бигоническая последовательность Низ 1вис. 21.8. Возможные частные случаи сравнения в сети НАБВ СБВАнкк[н] 0 при ть = 1, Р(тв/2)+1 приза = 2а, й > 1, ~О! Всрк ггосггеловатсггьнгзсть;!Б-' Ь жается рекурреитным соотношением решение которого имеет вид Р (тв) = 18 за. Бгтгвинссьая одноночная последовательность Битммческая гзгтслсзггвггтечьгггтсть Часть Ч11.
Избранные темы 812 — Вьете::,::,':'.; ~:: — р [ Бвтовввесввв ~ оотееоввтевьпость 0 '1 отсортировввнвЯ 1 оосвевовв тет|ьвость Рне. 27.9. Сравнивающая сеть Вргон!с Войтек[те[ лля те = 8 Таким образом, нуль-единичную бнтоническую последовательность можно отсортировать с помощью сети В~тояс соитии, глубина которой равна 1яп. Из утверждения, аналогичному нуль-единичному принципу, которое предлагается доказать в упражнении 27.3-6, следует, что с помощью такой сети можно отсортировать любую битоническую последовательность, состоящую из произвольных чисел. Упражнения 27.3-1. Сколько нуль-единичных битонических последовательностей длины и можно образовать? 27.3-2. Покажите, что сеть В[торлс Боктии[п], где и — степень двойки, содержит ст (и 18 и) сравнивающих устройств.
27.3-3. Опишите, как сконструировать битонический сортировщик глубиной О (1я и), если и не равно степени двойки. 27.3-4. Докажите, что если на вход полуфильтра подается битоническая последовательность, состоящая из произвольных чисел, то выходная последовательность обладает следующими свойствами: верхняя и нижняя половины выходной последовательности являются битоническими, и каждый Глава 27. Сортирующие сети 813 элемент из верхней половины не превышает по величине ни одного элемента из нижней половины. 27.3-5.
Рассмотрим две последовательности, состоящие из нулей и единиц. Докажите, что если каждый элемент одной из них не превышает по величине элементы другой последовательности, то одна из двух последовательностей является однородной. 27.3-б. Докажите такой аналог нуль-единичного принципа для битонических сортирующих сетей: сравнивающая сеть, которая может отсортировать любую битоническую последовательность из нулей н единиц, может также отсортировать любую битоническую последовательность, состоящую из произвольных чисел.
27.4 Объединяющая сеть Наша сортирующая сеть будет составлена из объединяющих сетей (тегй1пд пеьчогкз), в роли которых выступают сети, способные объединять две отсортированные входные последовательности в одну отсортированную выходную последовательность. Модифицируем сеть В~тоълс Бокткк[п], с тем чтобы создать объединяющую сеть Мккокк[п]. Как и в случае с битоническим сортировщнком, корректность работы объединяющей сети достаточно доказать для входных последовательностей, состоящих из нулей и единиц. В упражнении 27.4-1 предлагается обобщить это доказательство на случай произвольных входных значений. Идея объединяющей сети основывается на таком интуитивном соображении.
Если имеются две отсортированные последовательности, то в результате инвертирования второй последовательности и объединения ее с первой последовательностью получится бнтоническая последовательность. Например, пусть нуль-единичные последовательности Х и У имеют вид: Х = 00000111 и У = 00001111. После инвертирования последовательности У получаем Ук = 11110000.
Объединив последовательности Х и Ук, получим битоническую последовательность 0000011111110000. Таким образом, чтобы объединить две входные последовательности Х и У, достаточно выполнить бнгоническую сортировку последовательности Х, объединенной с последовательностью Ук. Чтобы составить сеть Мккокк[п], можно модифицировать первый полуфильтр, входящий в состав сети В~тоълс Бокткк[п]. Главная проблема в том, чтобы выполнить явное инвертирование второй половины входной последовательности. Чтобы объединить две заданные отсортированные последовательности (ам аз,..., а„7з) и (а„7з+ма„уз+э,...,а„), нужно добиться, чтобы выполнялась битоническая соРтиРовка последовательности (ам аз,...,а„7з,а„, а„м..., а„~ + ). Поскольку в первом полуфильтре сети В~тоълс Бокткк[п] сравниваются входные значения под номерами 1 и п/2 + 1 для всех 1 = 1,2,..., п/2, в первом моду- Часть Ч)1.
Избранные темы 814 Ь) Ьг Битоническвя последовательнопь 3 Ьа Ь5 Ьь Битоническая Ь, посл елователь ность ь, е~ Отеоргироввннвя в последовательнопь ез О5 Отсортированная аь Поеднговательносгь а) Ьг Битоническы Ь3 послелоаагель330суь Ь4 ь, ь, Битоническвя Ьб ПОСЛЕДОВатЕЛЬНОСП, Ьз ег аз Е4 Бипгннческнг послеловательн ость ат Еь б) Рис. 27.10. Сравнение первого модуля сети Мвковк[п] с первым модулем Ни.р Сьелнек[п] при п = 8 ле обьединяющей сети необходимо сравнивать входные значения под номерами г и тг — 1+ а. На рис. 27.10 показано данное соответствие. На первом этапе в сети МЕКОЕК[п] две монотонные входные последовательности (аг, аг,..., а„7г) " (ап7г+3 ап7г+г,,а„) преобразуются в битонические последовательности (Ь),Ьг,,ЬО7г) и (ЬО7г+ы Ь„гг+г,...,Ьп) (часть а рисунка). В части б этого рисунка проиллюстрирована эквивалентная операция в сети НАьр СьеАнек[п[.
Здесь битоннческая входная последовательность (аг, аг,..., ап гг, а„, ап г,..., а„гг+г) преобразуется в две битонические последовательности (Ьг, Ьг,..., ЬО~Д и (Ь„, Ь„),..., Ьп гг+3). Единственное отличие этой схемы заключается в том, что выходы в нижней части первого модуля сети МЕКСЕК[та] расположены в обратном порядке по сравнению с выходами обычного полуфильтра. Однако поскольку последовательность, полученная в результате инвертирования битонической последовательности, тоже является битоничесжгй, верхняя и нижняя половины последовательности, полученной на выходе первого модуля объединяющей сети, удовлетворяют свойствам леммы 27.3.
Таким образом„можно параллельно выполнить битоническую сортировку верхней и нижней частей последовательности, чтобы на выходе объединяющей сети получить отсортированную последовательность. Глава 27. Сортирующие сети 815 Ф- 0 0— Отсортироваяиал ] О— оосаеловиельяость 1 [ Отворен~валява в осл Етов атеА ь нс1ел ь /оОтсортироваяяал лослеловательность Рис. 27.11. Сеть, объединяющая лве входные отсортированные по- следовательности, в одну выходную отсортированную последователь- ность при и = 8 Получившаяся в результате объединяющая сеть показана на рис. 27.11.
Лишь первый модуль сети МикОнк[те] отличается от модуля сети В~тОьлс БОктин[те], следовательно, глубина обеих сетей равна 18 пи Сеть Минсни[тл] можно рассматривать как сеть В)тоьлс Зонтик[те], в которой первый полуфильтр изменен таким образом, что он сравнивает входные значения с номерами 1 и ть — 1+ 1 при е = = 1, 2,..., тл/2. В части а этого рисунка сеть разбита на модули; за первым модулем в ней следуют два параллельно расположенных модуля Вггоьлс Яоктнн[тл/2]. В части б изображена та же сеть, в которой рекурсия раскрыта подробнее.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
