Маргинальные свойства простых сортировок целочисленных массивов - page 8

А.Ф. Деон, Ю.И. Терентьев
8
При анализе данного метода используются обозначения, принятые
для сортировки методом парных сравнений. Инструкция int n1 = n – 1
занимает две операции:
1 1 2 SortPairMod SortPair
W W   .
При настройке главного цикла for (int i = 0; i < n1; i++) выпол-
няются 2,1
SortPairMod
W операций:
2,1 2,1 2 SortPairMod SortPair
W W   .
Кроме того, в максимальном случае на каждой итерации прово-
дится проверка условия i < n1 — одна операция и увеличивается ин-
декс i++ — две операции:
    1 1
2,2 max
0
1 2 3 1 .
n
SortPairMod
i
W n 

   
В теле главного цикла устанавливается флаг bool flag = true в пред-
положении, что оставшаяся часть массива будет упорядоченной. Уста-
новка флага занимает одну операцию. В минимальном случае главный
цикл выполняет только одну итерацию:
0
2,3,1min
0
1 1. SortPairMod
i
W

 
В максимальном случае флаг устанавливается на каждой итера-
ции главного цикла:
1 1
2,3,1max
0
1 1.
n
SortPairMod
i
W n 

   
Поиск текущего минимального элемента осуществляется под
управлением заголовка внутреннего цикла for (int j = n1; j > i; j– –).
До начала его итераций выполняются установка начального значения
int j = n1 — одна операция и предварительная проверка условия j > i —
одна операция. В минимальном случае выполняется только одна ите-
рация главного цикла:
  0
2,3,2 min
0
1 1 2. SortPairMod
i
W

  
В максимальном случае установки начальных значений внутрен-
него цикла выполняются на всех итерациях главного цикла:
    1 1
2,3,2 max
0
1 2 3 1 .
n
SortPairMod
i
W n 

   
Кроме того, на каждой итерации внутреннего цикла в заголовке
цикла выполняются одна операция на очередную проверку оконча-