Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 168
Текст из файла (страница 168)
В части а этого рисунка сеть разбита на модули; за первым модулем в ней следуют два параллельно расположенных модуля Вггоьлс Яоктнн[тл/2]. В части б изображена та же сеть, в которой рекурсия раскрыта подробнее. Возле проводов указаны примеры нуль-единичных величин, а отдельные модули выделены затенением. Упражнения 27.4-1. Докажите для объединяющих сетей утверждение, аналогичное нуль-единичному принципу. Другими словами, покажите, что сравнивающая сеть, которая объединяет две произвольные монотонно неубывающие последовательности из нулей и единиц, могут объединять две произвольные монотонно неубывающие последовательности, состоящие из любых чисел.
816 Часть ЧП. Избранные темы 27.4-2. Сколько различных нуль-единичных последовательностей необходимо подать на вход сравнивающей сети, чтобы проверить, что она действительно является объединяющей сетью? 27.4-3. Покажите, что любая сеть, которая объединяет один элемент с п — 1 отсортированными элементами, выдавая отсортированную последовательность длины п, должна иметь глубину не менее 18 и. * 27.4-4. Рассмотрим объединяющую сеть с входной последовательностью аз, аз, ..., а„для и, равных степени двойки, в которых две монотонные объединяемые последовательности имеют вид (аз, аз,..., а„-з) и (аг, а4, а„).
Докажите, что количество сравнений, которые выполняются в объединяющих сетях этого вида, равно П (и 18 п). Почему эта нижняя граница представляет интерес? (Указание: разбейте сравнивающие устройства на три множества.) * 27.4-5. Докажите, что для любой объединяющей сети, независимо от порядка входных последовательностей, требуется П (и 18 и) сравнивающих устройств. 27.5 Сортирующая сеть Теперь у нас имеются все инструменты, необходимые для построения сети, юторая способна отсортировать любую входную последовательность. В сортирующей сети Боктек[п] с помощью обьединяющей сети реализована параллельная версия сортировки слиянием, описанная в разделе 2.3.1.
Построение и работа сортирующей сети проиллюстрирована на рис. 27.12. На рис. 27.12а показана рекурсивная схема сети Боктек[п]. Последовательность из п входных элементов сортируется путем (параллельной) рекурсивной сортировки двух подпоследовательностей длиной п[2, каждая в двух модулях Боктвк[п/2].
Затем обе полученные в результате последовательности объединяются с помощью модуля Мвкапк[п]. Граничный случай рекурсии имеет место при и = 1. При этом 1-элементную последовательность можно отсортировать с помощью провода, потому что она уже отсортирована. На рис. 27.12б показан результат более подробного представления рекурсии, а на рис. 27.12в — сама сеть, полученная в результате замены блоков Мпкпев„изображенных на рис.
27.12б, реальными объединяющими сетями. Кроме того, на рис. 27.12в указаны глубины всех сравнивающих устройств, а возле проводов — примеры нуль-единичных значений. В сети Боктнк[п] данные проходят 18п этапов. Каждый отдельный входной элемент сети представляет собой уже отсортированную одноэлементную последовательность. Первый модуль сети Боктпк[п] состоит из и/2 копий подсети Мккпик[2], которые подключены параллельно и объединяют пары 1-элементных Глава 27.
Сортирующие сети 817 з 2 3 4 я 4 4 5 5 6 Гл>сина ! Рнс. 27.12. Сортирующяя сеть Зоктвк[о], построенная лугам рекурсивного совмещения обьелиняющих сетей последовательностей в отсортированные последовательности из двух элементов. Второй модуль состоит из а/4 копий подсети Мнкснк[4], объединяющих пары этих двухзлементных отсортированных последовательностей в отсортированные последовательности из четырех элементов.
В общем случае модуль под номером Часть Ч11. Избранные темы 818 lс, где й = 1,2,...,18п, состоит из и/2" копий подсети Мижнк[2"], объединяющих пары 2" '-элементных отсортированных последовательностей в отсортированные последовательности длины 2". На выходе последнего модуля выдается одна отсортированная последовательность, содержащая все входные значения. По индукции можно показать, что такая сеть сортирует все нуль-единичные последовательности, а значит, согласно нуль-единичному принципу (теорема 27.2), она способна сортировать произвольные значения.
Можно провести рекурсивный анализ глубины сортирующей сети. Глубина Р (и) сети Боктнк[п] равна сумме глубины Р (и/2) подсети Боктвк[п/2] (всего имеется две копии этой подсети, но они работают параллельно) и глубины 18 и модуля Микаил[п]. Следовательно, глубина сети Боктик[п] выражается рекуррентным соотношением 0 при и = 1, Р(п/2)+18п при п = 2", й > 1, решение которого имеет вид Р (п) = 9 (18~ п) . (Здесь использована версия основного метода из упражнения 4.4-2.) Таким образом, в параллельной сети и чисел можно отсортировать за время О (18~ и).
Упражнения 27.5-1. Сколько сравнений выполняется в сети Боктек[п]? 27.5-2. Покажите, что глубина сети Болтик[п] равна (18 п) (18 и+ 1)/2. 27.5-3. Предположим, что всего имеется 2п элементов (аы аг,..., аг„) и нужно разбить их на две части, в одной из которых содержалось бы п меньших элементов, а в другой — п больших. Докажите, что это можно сделать путем увеличения на единицу глубины сети, выполняющей раздельную сортировку последовательностей (аы аг,..., пь) и (а +ы а +г,, агь). * 27.5-4.
Пусть Я (й) — глубина сортирующей сети на 1с входов, а М (1с) — глубина обьединяющей сети на 2й входов. Предположим, что задана последовательность из п чисел, которую нужно отсортировать. Также известно, что каждое число находится в пределах й позиций от правильного положения, которое оно займет после сортировки. Покажите, что п таких чисел можно отсортировать с помощью сети глубиной Я (к) + 2М (й). * 27.5-5. Элементы матрицы тп х т можно отсортировать путем )с-кратного повторения описанной ниже процедуры. 1) Сортировка всех нечетных строк в порядке возрастания.
2) Сортировка всех четных строк в порядке убывания. Глава 27. Сортирующие сети 819 3) Сортировка всех столбцов в порядке возрастания. Скольш итераций потребуется выполнить в этой процедуре сортировки? В каком порядке следует считывать матричные элементы после )ь итера- ций, чтобы получилась отсортированная выходная последовательность? Задачи а) Покажите, что любая сортирующая транспозиционная сеть с п входами содержит Й (пз) сравнивающих устройств. б) Докажите, что транспозиционная сеть с и входами является сортирующей тогда и только тогда, когда она сортирует последовательность (гз, и — 1,..., 1).
(Указание: используйте метод математической индукции, аналогично доказательству леммы 27.1.) Нечеязно-четная сортяррющяя сеть (о<И-етеп зогйпй пепчогК) на и входов (аз, аз,..., а,з) — это транспознционная сортирующая сеть с и уровнями сравнивающих устройств, соединенных между собой по схеме "кирпичной кладки" (рис. 27.13). Как видно из рисунка, при з = = 1,2,..., и и ь( = 1, 2,..., гз линия з соединена сравнивающим устройством на глубине Н с линией 3 = з + ( — 1)ь+", если 1 < 3 < и. в) Докажите, что нечетно-четные сортнрующие сети действительно выполняют сортировку. ь! ьз ьз ьз ь, ьз ьв вз ь4 Оз Рис.
27.13. Нечетно-четнвя сор- тирующая сеп» на 8 входов 27-1. Транспозицнонные сортирующие сети Сравнивающая сеть является траясяозизЬионяой (1гапзроз(йоп пепчогк), если каждое сортирующее устройство в ней соединяет соседние линии, как в сети, изображенной на рис. 27.3. 820 Часть Ч11. Избранные темы 27-2. Нечетно-четная объединяющая сеть Батчера (ВаГсЬег) В разделе 27.4 было показано, как построить объединяющую сеть на основе битонической сортировки. В этой задаче будет сконструирована нечетно-четная объединяющая сеть (гхЫ-ечеп шег81п8 пеГчгог1с). Предполагается, что п равно степени двойки, а задание заключается в том, чтобы обьедииить отсортированную последовательность, элементы которой подаются на линии (аг, аз,..., а„), с отсортированной последовательностью, элементы которой подаются на линии (а„+г, а„+з,..., аз„).
Если и = 1, то сравнивающее устройство размещается между линиями а~ и аз. В противном случае по принципу рекурсии составляются две нечетно-четные объединяющие сети, которые работают параллельно. Первая из них объединяет последовательность, которая подается иа линии (аг,аз,...,а„г), с последовательностью, которая подается на линии (а„~ма„+з,..., аз„г) (нечетные элементы). Вторая сеть выполняет ту же самую операцию над последовательностями (аз, а4,..., а„) и (ач+з, ач+4,...,аз„) (четные элементы). Чтобы скомбинировать две отсортированные последовательности, сравнивающие устройства помещаются между линиями аз; и агя+г при г = 1, 2,..., и — 1. а) Изобразите объединяющую сеть на 2и входов при и = 4.
б) Профессор предложил обьединять две отсортированные последовательности, полученные путем рекурсивного объединения, помещая сортирующие устройства не между линиями агя и аьч+г для 1 = = 1, 2,..., п — 1, а между линиями аьч ~ и агя для 4 = 1, 2,..., и. Нарисуйте схему такой сети на 2п входов при п = 4 и приведите контрпример, из которого видно, что профессор ошибается, и получившаяся в результате сеть не является объединяющей. На этом же примере покажите, что объединяющая сеть на 2и входов, описанная в части а, работает правильно. в) Докажите с помощью нуль-единичного принципа, что любая нечетко-четная объединяющая сеть на 2п входов действительно является объединяющей сетью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
