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