Специальные методы сортировки a

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


Рис. 11.4. Сортирующая сеть
Ключи перемещаются по линиям сортирующей сети слева направо. По пути им встречаются компараторы, которые при необходимости обменивают ключи, в результате чего меньший из двух ключей поднимается на верхнюю линию. В данном примере на двух верхних линиях обмениваются ключи B и C, потом на двух нижних линиях обмениваются A и D, затем обмениваются A и B и т.д., и в конце ключи оказываются упорядоченными сверху вниз. В этом примере обмен ключей выполняют все компараторы, за исключением четвертого. Такая сеть способна отсортировать любые перестановки из четырех ключей.
На рис. 11.4 показана простая сортирующая сеть для четырех ключей. Обычно сортирующая сеть для N элементов изображается в виде последовательности N горизонтальных прямых линий и компараторов, соединяющих пары этих линий. Сортируемые ключи как бы проходят по сети слева направо, а если встречается компаратор, он при необходимости производит обмен этих чисел, чтобы меньшее из двух чисел оказалось вверху.
До построения реальной сортирующей машины, работающей по этой схеме, нужно решить ряд вопросов. Например, не описан метод кодирования входных данных. Один из способов - рассматривать каждую линию связи на рис. 11.4 как группу линий, передающих по одному биту данных, так что все биты ключа распространяются по линии одновременно. Другой подход заключается в том, что данные поступают на входы компараторов по одной линии бит за битом (сначала наиболее значащие биты). Кроме того, совершенно не затронут вопрос синхронизации: должны быть предусмотрены механизмы, препятствующие срабатыванию компараторов до готовности входных данных. Сортирующие сети - это полезные абстракции, поскольку они позволяют нам отделять детали реализации от проектных решений более высокого уровня наподобие минимизации количества компараторов. Более того, как мы убедимся в разделе 11.5, абстракция сортирующей сети может быть полезной и в приложениях, отличных от построения непосредственно электронных схем.
Еще одним важным применением сортирующих сетей является использование их в качестве модели параллельных вычислений. Если два компаратора не используют для ввода данных одни и те же линии, то, очевидно, они могут работать одновременно. Например, сеть, изображенная на рис. 11.4, показывает, что четыре элемента могут быть отсортированы за три параллельных шага. На первом шаге могут одновременно работать компаратор 0-1 и компаратор 2-3, после чего на втором шаге могут одновременно работать компаратор 0-2 и компаратор 1-3, и на третьем шаге компаратор 2-3 завершает сортировку. Для любой заданной сети компараторы нетрудно сгруппировать в последовательность параллельных каскадов (parallel stage), состоящих из компараторов, которые могут работать одновременно (см. упражнение 11.17). Для наибольшей эффективности параллельных вычислений нужно разрабатывать сети с минимально возможным числом параллельных каскадов.
Программа 11.2 непосредственно соответствует сливающей сети для каждого N, но полезно ознакомиться и с прямым восходящим построением, изображенным на рис. 11.5.