Последовательный алгоритм пузырьковой сортировки сравнивает и обменивает соседние элементы в последовательности, которую нужно отсортировать. Для последовательности (a1, a2, ..., an) алгоритм сначала выполняет n-1 базовых операций "сравнения-обмена" для последовательных пар элементов (a1, a2), (a2, a3), ..., (an-1, an).

   В результате после первой итерации алгоритма самый большой элемент перемещается ("всплывает") в конец последовательности. Далее последний элемент в преобразованной последовательности может быть исключен из рассмотрения, и описанная выше процедура применяется к оставшейся части последовательности (a'1, a'2, ..., a'n-1).

   Как можно увидеть, последовательность будет отсортирована после n-1 итерации. Эффективность пузырьковой сортировки может быть улучшена, если завершать алгоритм в случае отсутствия каких- либо изменений сортируемой последовательности данных в ходе какой-либо итерации сортировки.

   Для распараллеливания пузырьковой сортировки используется модификация алгоритма, называемая метод чет-нечетной перестановки.Суть модификации состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода: в зависимости от четности или нечетности номера итерации сортировки для обработки выбираются элементы с четными или нечетными индексами соответственно, сравнение выделяемых значений всегда осуществляется с их правыми соседними элементами.

   Таким образом, на всех нечетных итерациях сравниваются пары

(a1, a2), (a3, a4), ..., (an-1,an) (при четном n),

(a2, a3), (a4, a5), ..., (an-2,an-1).

   После n-кратного повторения итераций сортировки исходный набор данных оказывается упорядоченным. Получение параллельного варианта для метода чет-нечетной перестановки уже не представляет каких-либо затруднений – сравнения пар значений на итерациях сортировки являются независимыми и могут быть выполнены параллельно.

   При общем рассмотрении алгоритма быстрой сортировки (the quick sort algorithm), предложенной Хоаром (C.A.R. Hoare), прежде всего следует отметить, что этот метод основывается на последовательном разделении сортируемого набора данных на блоки меньшего размера таким образом, что между значениями разных блоков обеспечивается отношение упорядоченности (для любой пары блоков все значения одного из этих блоков не превышают значений другого блока).

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

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

• выбрать каким-либо образом ведущий элемент и разослать его по всем процессорам системы (например, в качестве ведущего элемента можно взять среднее арифметическое элементов, расположенных на выбранном ведущем процессоре);
• разделить на каждом процессоре имеющийся блок данных на две части с использованием полученного ведущего элемента;
• образовать пары процессоров, для которых битовое представление номеров отличается только в позиции N, и осуществить взаимообмен данными между этими процессорами.

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

   Последовательный метод упорядочивания данных характеризуется квадратичной зависимостью сложности от числа упорядочиваемых данных, т.е. T1~n^2. Но для сортировки могут быть применены более эффективные последовательные алгоритмы, трудоемкость которых имеет порядок

  Определим теперь сложность рассмотренного параллельного алгоритма упорядочивания данных. Как отмечалось ранее, на начальной стадии работы метода каждый процессор проводит упорядочивание своих блоков данных (размер блоков при равномерном распределении данных равен n/p). Предположим, что данная начальная сортировка может быть выполнена при помощи быстродействующих алгоритмов упорядочивания данных, тогда трудоемкость начальной стадии вычислений можно определить выражением вида:

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

  Определим вначале вычислительную сложность алгоритма сортировки. На каждой из log2p итераций сортировки каждый процессор осуществляет деление блока относительно ведущего элемента, сложность этой операции составляет n/p операций (будем предполагать, что на каждой итерации сортировки каждый блок делится на равные по размеру части).

  При завершении вычислений процессор выполняет сортировку своих блоков, что может быть выполнено при использовании быстрых алгоритмов за (n/p)log2(n/p) операций.Таким образом, общее время вычислений параллельного алгоритма быстрой сортировки составляет

  Рассмотрим теперь сложность выполняемых коммуникационных операций. Общее количество межпроцессорных обменов для рассылки ведущего элемента на N-мерном гиперкубе может быть ограничено оценкой

  При используемых предположениях (выбор ведущих элементов осуществляется наилучшим образом) количество итераций алгоритма равно log2p, а объем передаваемых данных между процессорами всегда равен половине блока, т.е. величине (n/p)/2. При таких условиях коммуникационная сложность параллельного алгоритма быстрой сортировки определяется при помощи соотношения: