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

Рис. 11.8. Тасование в нечетно-четном слиянии Бэтчера
Непосредственная реализация программы 11.2 в виде сортирующей сети порождает сеть, насыщенную рекурсивными операциями тасования и обратного тасования (вверху). Эквивалентная реализация (внизу) использует только полные тасования.
На рис. 11.9 показана еще одна интерпретация рассматриваемого метода, которая вскрывает его базовую структуру.


Рис. 11.9. Слияние методом разбиения и чередования
Начав с двух отсортированных файлов в первом ряду, мы сливаем их с помощью повторения следующей операции:разбиваем каждый ряд на две равные части, чередуем полученные половины (слева) и выполняем операции сравнения-обмена над смежными по вертикали элементами из разных рядов (справа). Сначала было 16 столбцов и 1 ряд, затем 8 столбцов и 2 ряда, 4 столбца и 4 ряда, 2 столбца и 8 рядов и, наконец, 16 рядов и один столбец, который к этому моменту отсортирован.
Сначала мы записываем один файл под другим, далее сравниваем смежные по вертикали элементы и при необходимости выполняем их обмен так, чтобы меньший элемент находился выше большего. Затем мы делим каждый ряд на две равные части и чередуем половины этих рядов, после чего выполняем те же операции сравнения-обмена над данными во второй и третьей строках. В сравнении других пар рядов нет необходимости, поскольку они уже были отсортированы. Операция разбиения-чередования сохраняет упорядочение как рядов, так и столбцов. Эта операция сохраняет упорядоченность и всего файла: каждый шаг удваивает число рядов, сокращает наполовину число столбцов и сохраняет упорядоченность рядов, и в конечном итоге получается один полностью отсортированный столбец из N рядов. Связь между таблицей, представленной на рис. 11.9, и сетью, изображенной в нижней части рис. 11.8, заключается в том, что если развернуть таблицы по столбцам (за элементами первого столбца следуют элементы второго столбца и т.д.) то мы увидим, что преобразование, необходимое для перехода с одного шага на другой, и есть идеальное тасование.
Теперь с помощью абстрактной параллельной машины со встроенными соединениями идеального тасования (см. рис. 11.10) можно непосредственно реализовать сеть, подобную показанной в нижней части рис. 11.8. Такая машина на каждом шаге выполняет, как предписано алгоритмом, операции сравнения-обмена для некоторых пар смежных процессоров, после чего осуществляет идеальное тасование данных. Программирование этой машины сводится к определению, какие пары процессоров должны выполнять операции сравнения-обмена на каждом цикле.
На рис. 11.11 показаны динамические характеристики как восходящего метода, так и версии нечетно-четного слияния Бэтчера с полным тасованием.
Тасование - это важная абстракция, описывающая движение данных в алгоритмах " разделяй и властвуй " , и она возникает в различных задачах, не связанных с сортировкой. Например, если квадратная матрица размером 2ⁿ х 2ⁿ хранится в памяти по строкам, то n идеальных тасований транспонируют эту матрицу (преобразуют в упорядоченную по столбцам). Более важные примеры - быстрые преобразования Фурье и вычисление полиномов (см. часть 8). Каждая из этих задач может быть решена при помощи циклической машины идеального тасования, подобной показанной на рис. 11.10, но с более мощными процессорами. Можно даже обдумать вариант с использованием универсальных процессоров, способных выполнять прямое и обратное тасование (некоторые из машин этого типа были даже реально построены); к таким параллельным машинам мы еще вернемся в разделе 11.5.