Маргинальные свойства сортировки массивов методом дихотомической вставки
9
выполнения цикла. С учетом итераций внешнего цикла это займет
следующее количество операций:
(
)
(
)
1
4,2
1
1 1 2 1
n
j
W
n
−
=
= + = −
∑
.
Учитывая аналогичный вывод в разделе последовательной
вставки, в теле цикла сдвига будет затрачено следующее количество
операций:
(
)
(
)
1
1
4,3
1 1
1
7
1 2 4
7
1
2
m j
n
n
j
j
W
j
n n
= −
−
=
=
=
+ + = = −
∑∑ ∑
.
В последней инструкции
a
[
i
]
= r
сортируемое значение
запоминается в упорядоченной части массива:
(
)
1
4,4
1
2 2 1
n
j
W
n
−
=
= = −
∑
.
Складывая оценки составных частей четвертого этапа, получаем
следующий результат:
(
)
(
)
(
)
(
)
4
4,1
4,2
4,3
4,4
2
7
7 5
2 1 2 1
1 2 1
6.
2
2 2
W W W W W
n
n
n n
n
n n
= + + + =
= − + − + − + − = + −
Все инструкции в функции
SortInsertDich()
рассмотрены.
Минимальное количество операций имеет следующую оценку:
(
)
min
1
2
3 1 4 1 7 5
SortInsertDich
W
W W n
n
n
= + = − + − = −
.
Максимальное количество операций в функции
SortInsertDich()
оценивается следующим образом:
(
)
(
)
(
)
(
)
max
1
2
3
4
2
2
2
2
7 5
3 1 4 1 4 9]log [
1
6
2 2
7
17
9 1 ]log [
15.
2
2
SortInsertDich
W
W W W W
n
n
n n
n n
n n
n n
= + + + =
= − + − + +
− + + − =
= + −
+ −
Сравнительная оценка последовательной и дихотомической
сортировок.
По минимальному количеству операций обе технологии
одинаковые:
min
min
7 5;
7 5.
SortInsertSeq
SortInsertDich
W
n
W
n
= −
= −
