Учебное пособие москва мади 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. Типы параллельных алгоритмов
 
В процессе 
исследовании параллельных алгоритмов на графах для 
представления графов используются матрицы смежности.