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