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