Теория и практика параллельных вычислений
Пузырьковая сортировка
Алгоритм пузырьковой сортировки в прямом виде достаточно сложен для распараллеливания — сравнение пар соседних элементов происходит строго последовательно. Параллельный вариант алгоритма основывается на методе чет-нечетной перестановки, для которого на нечетной итерации выполнения сравниваются элементы пар
(a1,a2),(a3,a4),...,(an–1,an).
Если пара не упорядочена, то ее элементы переставляются. На четной итерации упорядочиваются пары
(a2,a3),(a4,a5),...,(an–2,an–1).
После n-кратного повторения подобных итераций массив оказывается отсортированным. Более подробная информация о параллельном варианте алгоритма приводится в лекции 9.
Задания и упражнения
- Запустите систему ПараЛаб и создайте новый эксперимент. Выберите пункт меню Задача и убедитесь, что в активном окне текущей задачей является задача сортировки. Откройте диалоговое окно выбора метода и посмотрите, какие алгоритмы сортировки могут быть выполнены на текущей топологии. Так как при создании эксперимента по умолчанию текущей топологией становится кольцо, то единственный возможный алгоритм – алгоритм сортировки пузырьком. Закройте диалоговое окно и вернитесь в основное меню системы ПараЛаб.
- Выполните несколько экспериментов, изменяя размер исходных данных. Для выполнения эксперимента выполните команду В активном окне пункта меню Выполнить. Проанализируйте временные характеристики экспериментов, которые отображаются в правой нижней части окна.
- Проведите несколько вычислительных экспериментов, изменяя количество процессоров вычислительной системы. Проанализируйте полученные временные характеристики.
