цикла будет выполнено
J
av
и
J
D
операций для равноупорядоченного
и
D
-
упорядоченного исходного массива:
J
av
=
z
av
X
k
=1
3
=
1
X
k
=1
3
= 3;
J
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
.
После перестановок очередных меньших и больших элементов вы-
полняются две инструкции условия для определения момента оконча-
ния формирования меньшей и большей групп. Оба условия
i >
=
j
и
a
[
i
]
==
a
[
j
]
затрачивают две операции. Всего во внешнем цикле
будет затрачено
C
av
или
C
D
операций для двух вариантов исходного
массива:
C
av
=
z
av
∙
2
= 1
∙
2
= 2;
C
D
=
z
D
∙
2
=
n
+ 1
2
∙
2
=
n
+ 1
.
Поскольку инструкции условия для прекращения внешнего цикла
выполняются раньше перестановки значений элементов, то количе-
ство перестановок будет на единицу меньше числа итераций внешнего
цикла. Каждая перестановка занимает по три операции запоминания.
Всего во внешнем цикле будет выполнено
E
av
и
E
D
операций для
каждого варианта исходного массива соответственно:
E
av
=
z
av
∙
3
−
1
= 1
∙
3
−
1
= 2;
E
D
=
z
D
∙
3
−
1
=
n
+ 1
2
∙
3
−
1
=
3
2
n
+
1
2
.
Внешний вечный цикл завершен. Далее проверяется необходи-
мость установки разделяющего значения. Эту операцию обозначим
как
F
2
av
для массива с одинаковыми значениями и как
F
2
D
для мас-
сива с
D
-
последовательностью:
F
2
av
= 1;
F
2
D
= 4
.
Если предположить, что все операции занимают одинаковое время,
что соответствует упорядочиванию массива целых чисел, то в функции
HoarePosPrint
( )
выполняются
HP
av
и
HP
D
операций при различных
вариантах исходного массива:
HP
av
=
F
1
+
I
av
+
J
av
+
C
av
+
E
av
+
F
2
av
=
= 5 + 3 + 3 + 2 + 2 + 1 = 14;
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
97
