Маргинальные свойства сортировки массивов методом дихотомической вставки
3
(
)
1
2
1
4 4 1
n
j
W
n
−
=
= = −
∑
.
На третьем этапе происходит поиск места вставки во внутреннем
цикле для левой упорядоченной части массива. Заголовок внутренне-
го цикла
for
(
i = j
–1;
i >=
0;
i– –
) контролирует итерации поиска с
конца упорядоченной части. Для этого выполняются следующие
операции: 1) установка начального значения
i = j–
1 с двумя
операциями на вычитание и запоминание; 2) одна операция на
проверку условия
i >=
0. Для всех итераций внешнего цикла здесь
будет затрачено следующее количество операций:
(
)
(
)
1
3,1
1
2 1 3 1
n
j
W
n
−
=
= + = −
∑
.
Кроме того, на каждой итерации внутреннего цикла в заголовке
цикла выполняется одна операция на очередную проверку окончания
цикла
i >=
0 и две операции на уменьшение переменной цикла
i– –
:
(
)
(
)
(
)
1 1
1
3,2
1 0
1
1 3
1 2
3 3 1 1
1
2 2
i j
n
n
j
j
n
W
j
n
n n
= − −
−
=
=
−
=
+ = = + −
= −
∑ ∑ ∑
.
Итерации внутреннего цикла ограничены инструкцией условия
if
(
a
[
i
]
< a
[
j
])
break
. В заголовке этой инструкции выполняются три
операции на базирование адресов элементов массива и сравнение.
Маргинальность задается минимальной и максимальной оценками.
Минимальный случай был учтен на предыдущем этапе в инструкции
if( a
[
j
–1]
< a
[
j
]
)continue
, когда значения в массиве упорядочены по
возрастанию. Максимальный случай соответствует полному
выполнению внутреннего цикла без срабатывания прерывания
break
в инструкции
if( a
[
i
]
< a
[
j
]
)break
, поскольку исходный массив
упорядочен наоборот. В максимальном случае во всех итерациях
будет выполнено следующее количество операций:
(
)
(
)
1 1
1
3,3
1 0
1
1 3
3 3 3 1 1
1
2 2
i j
n
n
j
j
n
W
j
n
n n
= − −
−
=
=
−
=
= = + −
= −
∑ ∑ ∑
.
Итак, на третьем этапе будет выполняться максимальное количе-
ство операций, если в массиве находятся значения, упорядоченные
наоборот:
(
)
(
)
(
)
2
3
3,1
3,2
3,3
3
3
3 1
1
1 3 3
2
2
W W W W n
n n
n n
n
= + + = − + − + − = −
.
