Вычислительная схема обобщенного алгоритма быстрой сортировки с
использованием топологии гиперкуб выглядит следующим образом (в общем виде):
Распределяем исходный набор данных между процессорами блоками одинакового
размера (в случае, если количество элементов в исходном наборе не кратно числу
процессоров вычислительной системы удобнее попросить пользователя
сгенерировать массив подходящей длины или включить в массив
некоторое количество "нейтральных элементов", которые после сортировки будут
удалены);
Выбираем ведущие элементы. Разбиваем исходный N – мерный гиперкуб
(множество процессоров) на 2^i подгиперкубов (i – номер итерации; i = 0, 1, …,
N-1). В каждом из образовавшихся подгиперкубов, в рамках одного из процессоров
(например, с наименьшим номером), выбираем ведущий (средний) элемент и
рассылаем его значение всем остальным процессорам подгиперкуба. Заметим,
что на i-ой итерации, каждый из подгиперкубов будут образовывать процессоры, в
битовых представлениях номеров которых различаются i-ые (слева) позиции;
На каждом процессоре разделяем имеющийся блок данных на две части с
использованием полученного ведущего элемента;
Образуем пары процессоров, для которых битовое представление их номеров
отличается только в позиции (i+1) (слева), и осуществляем взаимообмен данными
между этими процессорами; в результате таких пересылок данных, на процессорах,
для которых в битовом представлении номера бит позиции (i+1) равен 0, должны
оказаться части блоков со значениями, не превышающими значения ведущего
элемента; процессоры с номерами, в которых бит (i+1) равен 1, должны собрать,
соответственно, все значения данных, превышающие значение ведущего элемента.
После исчерпывания количества гиперкубов, состоящих из групп процессоров
(в каждой группе осталось по одному процессору)выполняем сортировку блоков
данных на каждом из процессоров вычислительной системы (для этого используем
последовательный вариант алгоритма быстрой сортировки, стандартная функция
qsort языка с++);
Пересылаем все куски массива с каждого процессора на один процессор и
склеиваем там массив из кусочков согласно номерам процессоров от которых эти
куски пришли.
Выполнив шаги (2) – (4) N раз, получим отсортированный набор данных, разбитый
на блоки, число которых равно числу процессоров. После этого, остается лишь
собрать все блоки в один.
