Теория и практика параллельных вычислений

         

Пузырьковая сортировка


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

(a1,a2),(a3,a4),...,(an–1,an).

Если пара не упорядочена, то ее элементы переставляются. На четной итерации упорядочиваются пары

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

После n-кратного повторения подобных итераций массив оказывается отсортированным. Более подробная информация о параллельном варианте алгоритма приводится в лекции 9.

Задания и упражнения

  1. Запустите систему ПараЛаб и создайте новый эксперимент. Выберите пункт меню Задача и убедитесь, что в активном окне текущей задачей является задача сортировки. Откройте диалоговое окно выбора метода и посмотрите, какие алгоритмы сортировки могут быть выполнены на текущей топологии. Так как при создании эксперимента по умолчанию текущей топологией становится кольцо, то единственный возможный алгоритм – алгоритм сортировки пузырьком. Закройте диалоговое окно и вернитесь в основное меню системы ПараЛаб.
  2. Выполните несколько экспериментов, изменяя размер исходных данных. Для выполнения эксперимента выполните команду В активном окне пункта меню Выполнить. Проанализируйте временные характеристики экспериментов, которые отображаются в правой нижней части окна.
  3. Проведите несколько вычислительных экспериментов, изменяя количество процессоров вычислительной системы. Проанализируйте полученные временные характеристики.



Содержание раздела