Необходимо построить теоретические оценки показателей
эффективности параллельных вычислений.
Сравнить полученные оценки с экспериментальными данными.
Метод решения
Последовательный алгоритм
Последовательный алгоритм
"пузырьковой" сортировки сравнивает и обменивает соседние элементы в
последовательности, которую нужно отсортировать. Для последовательности
(a1, a2, ..., an)
алгоритм сначала выполняет n-1 операций "сравнения-обмена"
(compare-exchange) для всех последовательных пар
элементов (a1, a2), (a2, a3), ..., (an-1,an). На этом шаге самый большой элемент перемещается в конец
последовательности. Последний элемент в преобразованной
последовательности затем исключается из сортировки, и
последовательность "сравнений-обменов" применяется к возникающей в результате сокращенной
последовательности (a'1, a'2, ...,
a' n-1).
