Четно-нечетная сортировка перестановками
Выше нам удавалось снизить стоимость алгоритмов за счет сокращения числа процессоров. Необходимое число процессоров можно уменьшить вдвое, воспользовавшись следующим способом сортировки, который сравнивает соседние значения и при необходимости переставляет их. for j = 1 to N / 2 do Parallel Start
for k= to N/ 2 do
Рк сравнивает M[2k -1] и M[2k if их порядок неправильный then переставить их end if end for к Parallel End Parallel Start
for k= to N/2- do
P[k] сравнивает M[2k и M[2k +1] if их порядок неправильный then переставить их end if endfor к Parallel End end for j
Рис. 9.6. Четно-нечетная параллельная сортировка
При каждом проходе этот алгоритм сначала сравнивает М с М2, М3 с М4, ..., MN_ 1 с Мдг. Затем М2 сравнивается с М3, М4 с М5, ..., MN_ 2 с MN_ ь
и элементы, стоящие в неправильном порядке, переставляются. Предположим теперь, что наименьший элемент стоит в списке последним. Первое сравнение переведет его в предпоследнюю позицию, второе - во вторую с конца. Каждый проход алгоритма сдвигает минимальный элемент списка на две позиции ближе к требуемому положению. Повторение цикла N /2 раз сдвигает минимальный элемент на N- 1 позицию и ставит его в нужное место.
На рис. 9.6 изображено выполнение этой процедуры сортировки на нашем списке 15, 18, 13, 12, 17, 11, 19, 16, 14. Строчки изображают результат либо нечетного (метка О), либо четного (метка Е) шага.
Все сравнения происходят параллельно, поэтому всякий проход цикла выполняет два сравнения и общее время работы равно O(N). Стоимость алгоритма равна величине N / 2 * O(N) - несколько меньше, чем у предыдущего алгоритма, но все равно порядка 0(N ).
Другие параллельные сортировки
Список без повторений можно отсортировать также с помощью подсчета. При сравнении каждого элемента списка со всеми остальными его элементами можно подсчитать, сколько в списке значений, меньших него, и определить тем самым правильное его положение: число меньших элементов следует увеличить на 1. В модели CREW PRAM с одним процессором на каждое входное значение местоположение каждого элемента можно определить за 0(N) сравнений. Нам требуется N процессоров, поэтому стоимость такого подхода равна 0(N2).
Существуют способы параллельного слияния двух списков, реализующие оптимальную стоимость O(N) при использовании не более чем N / log N процессоров. Разбив список на N / log N частей и отсортировав каждую из них эффективным последовательным алгоритмом сортировки, например Quicksort, можно затем параллельно слить эти части в общий список. Параллельное слияние можно также использовать и в сортировке слиянием.
