Маргинальные свойства простых сортировок целочисленных массивов
9
ния цикла
j > i
и две операции на уменьшение переменной цикла
j– –
.
В минимальном случае, когда массив уже упорядочен, выполняется
только одна итерация главного цикла:
1
0
1
2,3,3min
0
0
1 2 3 3 1 .
j n
n
SortPairMod
i
j i
z
W
n
Если исходный массив упорядочен по убыванию, то затрачива-
ется максимальное количество операций на
j > i
и
j– –
:
1 1
1 1 1
1 1
1
2,3,3max
0
0 1
0
3
1 2
3 3
1 .
2
n
n n
n
j n
SortPairMod
j i
i
i
z i
i
W
n i
n n
В теле внутреннего цикла заголовок инструкции условия
if (a[j] <
< a[j – 1])
сравнивает значения пары соседних элементов
a[j] < a[j – 1]
в неупорядоченной части массива — три операции. На всех итераци-
ях внутреннего цикла заголовок инструкции условия затрачивает
2,3,4 min
SortPairMod
W
и
2,3,4 max
SortPairMod
W
операций:
1
0
1
2,3,4 min
0
1
3
3 3 1 ;
j n
n
SortPairMod
i
j i
z i
W
n
1
1 1
1 1 1
1 1
2,3,4 max
0
0 1
0
3
3
3 3
1 .
2
j n n
n n
n
SortPairMod
i
j i
i
z i
i
W
n i
n n
В минимальном случае тело инструкции условия не выполняется.
Если элементы исходного массива расположены в обратном
порядке, то на каждой итерации внутреннего цикла выполняется пе-
рестановка значений с помощью инструкции
int r = a[j]
— две опе-
рации, инструкции
a[j] = a[j – 1]
— четыре операции и инструкции
a[j – 1] = r
— три операции; всего девять операций:
1 1 1
1 1 1
1 1
2,3,5 max
0 1
0 1
0
9
2 4 3
9 9
1 .
2
n n
n n
n
SortPairMod
i
j i
i
j i
i
W
n i
n n
В конце тела главного цикла выполняется проверка флага в ин-
струкции условия
if (flag) break
— одна операция. В минимальном
случае сортировку далее проводить не следует:
0
2,4 min
0
1 1.
SortPairMod
i
W
В максимальном случае проверка флага выполняется на каждой
итерации главного цикла:
1 1
2,4 max
0
1 1.
n
SortPairMod
i
W
n
Таким образом,
маргинальные свойства сортировки модифици-
рованным методом парных сравнений (пузырька)
оцениваются сум-
