11.4. Показать, что неветвящаяся программа, которая сортирует N различных ключей, сможет отсортировать N ключей, которые не обязательно различны.

1>11.5. Показать, как неветвящаяся программа, приведенная в тексте, сортирует каждую из щести перестановок чисел 1, 2 и 3.

о 11.6. Приведите пример неветвящейся программы, которая выполняет сортировку четырех элементов.

11.7. Доказать лемму 11.1. Совет: Показать, что если программа не способна выполнить сортировку некоторого входного массива с произвольными ключами, то существует некоторая последовательность типа 0-1, которую она также не может отсортировать.

1>11.8. Показать, как выполняется слияние ключей AEQSUYEINOSTc помощью программы 11.2 в стиле примера, представленного на диаграмме рис.11.2.

1>11.9. Выполнить упражнение 11.8 для ключей AESYEINOQSTU.

о 11.10. Выполнить упражнение 11.8 для ключей 100111000001010 0.

11.11. Эмпирически выполнить сравнение времени выполнения сортировки слиянием Бэтчера аналогичным параметром стандартной нисходящей сортировки слиянием (программы 8.3 и 8.2) для TV = 10 10 10 и 10

11.12. Предложите реализации функций compexch, shuffle и unshuffle, которые заставляют программы 11.2 и 8.3 работать в режиме непрямой сортировки (см. раздел 6.8).

о 11.13. Предложите реализации функций compexch, shuffle и unshuffle, которые заставляют программы 11.2 и 8.3 печатать для заданного N неветвящуюся программу сортировки N элементов. Вы можете воспользоваться вспомогательным глобальным массивом для отслеживания значений индексов.

11.14. Если мы представим второй файл из предназначенных для слияния в обратном порядке, мы получим битонную {bitonic) последовательность в соответствии с определением, данным в разделе 8.3. Внеся изменения в заключительный цикл программы 11.2 так, чтобы он начинался с 1, а не с 1 + 1, мы получим программу, которая сортирует битонные последовательнсти. Показать, как с помощью этого метода выполняется слияние ключей AESQUYTSONIEb стиле примера, показанного на диаграмме на рис. 11.2.

11.15. Доказать, что модификация программы 11.2, описанная в упражнении 11.14, способна выполнить любой битонной последовательности.

11.2. Сети сортировки

Простейшей моделью для изучения неадаптивных алгоритмов сортировки является абстрактная машина, которая способна осуществлять доступ к данным только с помощью операций сравнения-обмена. Такая машина называется сетью сортировки {sorting network). Сеть сортировки построена из атомарных модулей сравнения-обмена {compare-exchange modules) или компараторов {comparators), которые соединены между собой линиями связи таким образом, что становится возможным выполнение полной сортировки общего вида.

С В О

На рис. 11.4 показана простая сеть, выполняющая сортировку четырех ключей. Обычно мы изображаем сеть сортировки элементов в виде последовательности горизонтальных прямых линий, при этом каждый компаратор соединен с двумя линиями. Можно считать, что сортируемые ключи проходят по сети справа налево, при этом при необходимости происходит обмен пары чисел, в результате которого меньшее из двух чисел подымается вверх всякий раз, когда на их пути возникает компаратор.

Необходимо снять целый ряд вопросов, прежде чем станет возможным построение реальной сортирующей машины, работающей по этой схеме. Например, не описан метод кодирования входов. В рамках одного из подходов каждую связь на рис. 11.4 можно рассматривать как группу линий, каждая такая линия несет один бит данных, следовательно, все биты ключа распространяются по линии одновременно. Другой подход заключается в том, что данные поступают на входы компараторов по одной линии побитно, т.е. 1 бит за единицу времени (первыми идут наиболее значащие биты). Кроме того, совершенно не затрагивался вопрос синхронизации: должны быть предусмотрены механизмы, препятствующие срабатыванию

компараторов, прежде чем поступят входйые данные. Сети сортировки представляют собой полезные абстракции, поскольку они позволяют нам отделять детали реализации от проектных решений более высокого порядка, таких как, например, минимизация числа компараторов. Более того, как мы убедимся в разделе 11.5, абстрактное понятие сети сортировки может быть с пользой применено и в приложениях, отличных от построения электронных схем различного назначения.

Еще одним важным применением сетей сортировки является модель параллельных вычислений. Если два компаратора не используют одних и тех же линий для ввода данных, то мы полагаем, что они могут работать одновременно. Например, сеть, изображенная на рис. 11.4, показывает, что четыре элемента могут быть отсортированы за три параллельных шага. Компаратор 0-1 и компаратор 2-3 могут работать одновременно на первом шаге, после чего компаратор 0-2 и компаратор 1-3 могут одновременно работать на втором шаге, а компаратор 2-3 завершает сортировку на третьем шаге. Для любой заданной сети нетрудно сгруппировать компараторы в последовательность параллельных каскадов {parallel stage), каждый из которых состоит из компараторов, которые могут работать одновременно (см. упражнение 11.17). Чтобы параллельные вычисления были эффективными, нашей задачей становится разработка сетей с минимально возможным числом параллельных каскадов.

РИСУНОК 11.4. СЕТЬ СОРТИРОВКИ

Ключи перемещаются по линиям сети сортировки слева направо. Компараторы, которые они встречают на своем пути, производят при необходимости обмен ключей, в результате которого меньший из двух ключей поднимается на верхнюю линию. В рассматриваемом примере на двух верхних линиях производится обмен ключей В и С, за ним следует обмен Аи Вна двух нижних линиях, затем происходит обмен Аи В и так далее, так что в конечном итоге ключи предстают перед нами отсортированными сверху вниз. В этом примере все компараторы, за исключением четвертого, выполняют операцию обмена. Такая сеть способна отсортировать любые перестановки из четырех ключей.

Программа 11.2 непосредственно соответствует сети слияния для каждого N, в то же время нам полезно ознакомиться с прямой восходящей структурой, изображенной на рис. 11.5. Чтобы построить сеть слияния размера Лмы воспользуемся двумя копиями сети размером N/2; одна из них предназначена для линий с четными номерами, а другая - для линий с нечетными номерами. Поскольку соответствующие два набора компараторов не пересекаются, мы можем разместить их таким образом, чтобы обе эти сети чередовались. После этого мы расставим компараторы между линиями 1 и 2, 3 и 4 и т.д. Чередование нечетных и четных линий заменяет идеальное тасование, использованное в программе 11.2. Доказательство того, что эти сети выполняют слияние должным образом, аналогично доказательствам лемм 11.1 и 11.2, для которых применялся принцип нулей и единиц. На рис.11.6 показан пример выполнения слияния этого типа.

Программа 11.3. является восходящей реализацией слияния Бэтчера без операции тасования, соответствующей сетям, представленным на рис. 11.5. Эта программа представляет собой компактную и элегантную обменную (не использующую дополнительного пространства оперативной памяти) функцию слияния, которую, возможно, легче понять, если считать ее чередующимся представлением сетей, в то же время прямое доказательство того, что она правильно завершает задачу слияния, само по себе очень интересно. Мы проведем исследование одного такого доказательства в конце этого раздела.

РИСУНОК 11.5. НЕЧЕТНО-ЧЕТНОЕ СЛИЯНИЕ БЭТЧЕРА

Показанные на этом рисунке различные представления сетей на четыре (сверху), восемь (в центре) и 16 (внизу) линий служат иллюстрацией рекурсивной структуры, положенной в основу сети. Слева показаны прямые представления конструкции сети размера N с двумя копиями сетей размера N/2 (одна для линий с четной нумерацией, другая для линий с нечетной нумерацией) плюс каскад компараторов, соединенных с линиями 1 и 2, 3 и 4, 5 и 6 и т.д. Справа показаны более простые сети, которые были получены нами из сетей, изображенных слева, путем группирования компараторов одинаковой длины; такое группирование стало возможным в связи с тем, что мы можем перемещать компараторы, установленные на нечетных линиях, мимо компараторов на нечетных линиях, не нарушая их работы.

021�7537