А.Ф. Деон, Ю.И. Терентьев
6
В теле функции
SortPair( )
выполняется инструкция
int n1 = n – 1
,
при этом затрачиваются
1
SortPair
W
операций:
1
1
1
2.
SortPair
SortExchange
SortChoice
W W
W
Далее в заголовке главного цикла
for (int i = 0; i < n1; i++)
до
начала итераций выполняются
2,1
SortPair
W
операций:
2,1
2,1
2,1
2.
SortPair
SortExchange
SortChoice
W W
W
На каждой итерации в заголовке цикла выполняются
2,2
SortPair
W
операций:
1 1
2,2
2,2
2,2
0
1 2 3 1 .
n
SortPair
SortExchange
SortChoice
i
W W
W
n
Поиск текущего минимального элемента осуществляется под
управлением заголовка внутреннего цикла
for (int j = n1; j > i; j– –)
.
До начала итераций этого цикла выполняются
2,3,1
SortPair
W
операций:
1 1
2,3,1
0
1 1 2 1 .
n
SortPair
i
W
n
Кроме того, на каждой итерации внутреннего цикла в заголовке
цикла выполняются одна операция на очередную проверку оконча-
ния цикла
j > i
и две операции на уменьшение переменной цикла
j– –
:
1
1 1
1 1 1
1 1
2,3,2
0
0 1
0
3
1 2
3 3
1
1 .
2
j n
n
n n
n
SortPair
i
j i
i
z i
i
W
n i
n n
В теле внутреннего цикла заголовок инструкции условия
if (a[j] <
< a[j – 1])
сравнивает значения пары соседних элементов
a[j] < a[j – 1]
в неупорядоченной части массива — три операции. На всех итерациях
внутреннего цикла заголовок инструкции условия затрачивает
2,3,3
SortPair
W
операций:
1
1 1
1 1 1
1 1
2,3,3
0
0 1
0
3
3
3 3
1 .
2
j n
n
n n
n
SortPair
i
z i
i
j i
i
W
n i
n n
В минимальном случае тело инструкции условия не выполняется.
В максимальном случае на каждой итерации внутреннего цикла
осуществляется перестановка значений с помощью инструкции
int r =
= a[j]
— две операции, инструкции
a[j] = a[j – 1]
— четыре операции
и инструкции
a[j – 1] = r
— три операции; всего девять операций:
1 1 1
1 1 1
1 1
2,3,4 max
0 1
0 1
0
9
(2 4 3)
9 9
1 .
2
n n
n n
n
SortPair
i
j i
i
j i
i
W
n i
n n
