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