в массиве:
n
= 2
cc
= 1
ci
= 0
cj
= 0
n
= 5
cc
= 3
ci
= 2
cj
= 2
n
= 11
cc
= 6
ci
= 5
cj
= 5
n
= 23
cc
= 12
ci
= 11
cj
= 11
n
= 47
cc
= 24
ci
= 23
cj
= 23
Итак, для подсчета минимального и максимального числа опе-
раций
1
при поиске места вставки по Хоару необходимо произвести
расчеты для исходного массива, который содержит либо одинаковые
значения, либо значения
D
-
последовательности. Установку разделя-
ющего элемента выполняет функция
HoarePosPrint
( ).
В теле данной
функции выполняются начальные действия
Typev = a
[
right
],
inti = left
,
intj = right – 1
,
intm = j
,
на которые затрачивается
F
1
операций для
запоминания и вычитания:
F
1
= 5
Количество итераций вечного цикла обозначим как
z
av
для массива
из
n
элементов с одинаковыми значениями и как
z
D
для массива с
D
-
последовательностью:
z
av
= 1;
z
D
=
n
+ 1
2
.
В теле внешнего вечного цикла
while
(
true
)
выполняется первый
внутренний цикл
while
(
a
[
i
]
< v
&&
i < m
)
++i
для группы мень-
ших элементов. На каждой итерации внутреннего цикла выполняется
три или пять операций: сравнение
a
[
i
]
<
v
,
сравнение
i < m
,
булева
конъюнкция
&&
и увеличение индекса
++i
.
С учетом внешнего ци-
кла всего будет выполнено
I
av
и
I
D
операций для соответствующих
значений исходного массива.
lI
av
=
z
av
X
k
=1
3
=
1
X
k
=1
3
= 3;
I
D
=
z
D
X
k
=1
3
+
z
D
−
1
X
k
=1
(2
+ 3) = 3
z
D
+ 5(
z
D
−
1)
= 8
n
+ 1
2
−
5
= 4
n
−
1
.
Затем выполняется второй внутренний цикл
while
(
v < a
[
j
]&&
j >
lef t
)
–
j
для группы больших элементов. Всего за время внешнего
1
С е д ж в и к Р. Фундаментальные алгоритмы на С++: Анализ: Структуры дан-
ных: Сортировка: Поиск: пер. с англ. – СПб.: ООО ДианаСофтЮП, 2002. – 688 с.
96
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
