Маргинальные свойства простых сортировок целочисленных массивов
11
В теле функции
SortShift( )
выполняется инструкция
int n1 = n – 1
,
при этом затрачиваются
1
SortShift
W
операций:
1
1
2.
SortShift
SortPair
W W
Далее в настройке заголовка главного цикла
for (int i = 0; i < n1;
i++)
выполняются
2,1
SortShift
W
операций:
2,1
2,1
2.
SortShift
SortPair
W W
Кроме того, на каждой итерации в заголовке цикла выполняются
2,2
SortShift
W
операций:
1 1
2,2
2,2
0
1 2 3 1 .
n
SortShift
SortPair
i
W W
n
В теле цикла инструкция
int k = i
фиксирует индекс позиции
опорного элемента. Количество этих операций
1 1
2,3
0
1 1.
n
SortShift
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
SortShift
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
SortShift
i
j i
i
W
n i
n n
В теле первого внутреннего цикла заголовок инструкции усло-
вия
if (a[j] < a[k])
сравнивает текущее минимальное значение
a[k]
с очередным значением элемента
a[j]
в неупорядоченной части мас-
сива — три операции. На всех итерациях первого внутреннего цикла
заголовок инструкции условия затрачивает
2,4,3
SortShift
W
операций:
1 1 1
1 1
2,4,3
0 1
0
3
3 3
1
1 .
2
n n
n
SortShift
i
j i
i
W
n i
n n
В минимальном случае тело инструкции условия не выполняется.
