Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

М
1
и М
2
; М
3
и М
4
; …, М
N ­ 1
и М
N
выполняется при 
каждом проходе алгоритма. Далее выполняется сравнение пар 
М
2
 и М
3
; М
4
 и 
М
5
; …, М
N ­ 2
 и М
N-2
.
В случае необходимости выполняется перестановка. На 
рис.33 представлен случай расположения наименьшего элемента в конце 
списка. За каждый проход
осуществляется сдвиг элемента на две позиции в 
сторону правильного положения. Элемент ставится в нужное место путем 

---

101 
сдвига на 
N-1
позицию 
N/2
раз при повторении цикла. За один проход цикла 
выполняются две операции сравнения. Рисунок иллюстрирует применение 
процедуры для списка 15, 18, 13, 12, 17, 11, 19, 16, 14. Символом «О» 
помечены нечетные шаги. Символом «E» - четные.
Стоимость алгоритма составляет 
N/2 * O(N)
. Вычислительная 
сложность - 
O(N
2
).
Общее время работы составляет 
O(N).
Глава 11. Типы параллельных алгоритмов 
В процессе 
исследовании параллельных алгоритмов на графах для 
представления графов используются матрицы смежности. 
11.1. Параллельный алгоритм поиска кратчайшего пути
Определим матрицу смежности взвешенного графа:
Рис. 33. Выполнение процедуры сортировки на списке 15, 18, 13, 12, 17, 11, 19, 16, 14 
(19)

---

102 
На рис. 34 изображен взвешенный граф и его матрица смежности.
В матрице смежности представлены прямые пути между вершинами 
графа, т. е. пути, состоящие из одного ребра. Восстановим кратчайшие пути 
по графу, состоящие из произвольного числа ребер, по матрице смежности. В 
исходной матрице