Параллельное обобщение алгоритма быстрой сортировки может быть
получено для вычислительной системы с топологией в виде p-мерного гиперкуба
(т.е. n=2p). Пусть, как и ранее, исходный набор данных распределен
между процессорами блоками одинакового размера N/n; результирующее расположение
блоков должно соответствовать нумерации процессоров гиперкуба. Возможный способ
выполнения первой итерации параллельного метода при таких условиях может
состоять в следующем:
• выбрать ведущий элемент и разослать его по всем процессорам системы
• разделить на каждом процессоре имеющийся блок данных на две части с
использованием полученного ведущего элемента;
•образовать группу процессов, в группе осуществить обмен данными между
процессами симметричными относительно центра группы, элементы которые
меньше ведущего элемента перемещаются в процессы из левой полугруппы, а которые
больше в правую.
В результате выполнения такой итерации
сортировки исходный набор оказывается разделенным на две части, одна из которых
(со значениями меньшими, чем значение ведущего элемента) располагается на
процессорах, левой полугруппы. Таких процессоров всего n/2 и, таким образом,
исходный p -мерный гиперкуб также оказывается разделенным на два гиперкуба
размерности p-1. К этим подгиперкубам, в свою очередь, может быть параллельно
применена описанная выше процедура. После p -кратного повторения подобных
итераций для завершения сортировки достаточно упорядочить блоки данных,
получившиеся на каждом отдельном процессоре вычислительной системы.
В качестве ведущего элемента целесообразнее будет выбирать
средний элемент на первом процессе вычислительной системы. Выбираемый подобным
образом ведущий элемент в отдельных случаях может оказаться более близок к
реальному среднему значению всего сортируемого набора, чем какое-либо другое
произвольно выбранное значение.
