Теория и практика параллельных вычислений
Алгоритм чет-нечетной перестановки
Алгоритм пузырьковой сортировки в прямом виде достаточно сложен для распараллеливания – сравнение пар значений упорядочиваемого набора данных происходит строго последовательно. В связи с этим для параллельного применения используется не сам этот алгоритм, а его модификация, известная в литературе как метод чет-нечетной перестановки (the odd-even transposition method) – см., например, [[51]]. Суть модификации состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода: в зависимости от четности или нечетности номера итерации сортировки для обработки выбираются элементы с четными или нечетными индексами соответственно, сравнение выделяемых значений всегда осуществляется с их правыми соседними элементами. Таким образом, на всех нечетных итерациях сравниваются пары
(a1, a2), (a3, a4), ..., (an-1,an) (при четном n),
а на четных итерациях обрабатываются элементы
(a2, a3), (a4, a5), ..., (an-2,an-1).
После n-кратного повторения итераций сортировки исходный набор данных оказывается упорядоченным.
Алгоритм 9.2. Последовательный алгоритм чет-нечетной перестановки
// Алгоритм 9.2 // Последовательный алгоритм чет-нечетной перестановки void OddEvenSort(double A[], int n) { for (int i = 1; i < n; i++) { if (i % 2 == 1) { // нечетная итерация for (int j = 0; j < n/2 - 2; j++) compare_exchange(A[2*j + 1], A[2*j + 2]); if (n % 2 == 1) // сравнение последней пары при нечетном n compare_exchange(A[n - 2], A[n - 1]); } else // четная итерация for (int j = 1; j < n/2 - 1; j++) compare_exchange(A[2*j], A[2*j + 1]); } }
