Сортировка пузырьком

. Алгоритм пузырьковой сортировки в прямом виде достаточно сложен для распараллеливания – сравнение пар значений упорядочиваемого набора данных происходит строго последовательно. В связи с этим для параллельного применения используется не сам этот алгоритм, а его модификация, известная в литературе как метод чет-нечетной перестановки (odd-even transposition). Суть модификации состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода – в зависимости от четности или нечетности номера итерации сортировки для обработки выбираются элементы с четными или нечетными индексами соответственно, сравнение выделяемых значений всегда осуществляется с их правыми соседними элементами. Т.е., на всех нечетных итерациях сравниваются пары (x1,x2),(x3,x4),…,(xn-1,xn) (при четном n), на четных итерациях обрабатываются элементы (x2,x3),(x4,x5),…,(xn-2,xn-1). После -кратного повторения подобных итераций сортировки исходный набор данных оказывается упорядоченным. Получение параллельного варианта для метода чет-нечетной перестановки уже не представляет каких-либо затруднений – сравнение пар значений на итерациях сортировки любого типа являются независимыми и могут быть выполнены параллельно. Для пояснений такого параллельного способа сортировки в табл приведен пример упорядочения данных при n=8, p=4,(т.е. блок значений на каждом процессоре содержит элементов). В первом столбце таблицы приводится номер и тип итерации метода, перечисляются пары процессоров, для которых параллельно выполняются операция "сравнить и разделить"; взаимодействующие пары процессоров выделены в таблице двойной рамкой. Для каждого шага сортировки показано состояние упорядочиваемого набора данных до и после выполнения итерации. Таблица Пример сортировки данных параллельным методом чет-нечетной перестановки

Быстрая сортировка

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