int L = HoarePosPrint
<
int
>
(
a, 0, n-1 );
//
разделяющий
cout
<<
"
L = "
<<
L
<<
endl;
for(i = 0; i
<
n; i++ ) cout
<<
setw (4)
<<
a[i];
_
getch();
//
просмотр результата
}
D
-
последовательности в перестановках Хоара.
Для определения
количества операций, выполняемых в функции
HoarePosPrint
( ),
необ-
ходимо подсчитать количество итераций, выполняемых в вечном ци-
кле при поиске индекса разделяющего элемента. Для этого необходимо
выполнить программу
DH
01
в различных вариантах представления
исходного массива. Интерес представляют последовательности эле-
ментов, которые дают минимальное и максимальное число итераций в
вечном цикле. В качестве примера ниже показана последовательность
с одинаковыми элементами:
5 5 5 5 5
В этой последовательности одна итерация вечного цикла, посколь-
ку отсутствует необходимость в перестановке и упорядочивать нечего.
В следующей последовательности на правой грани находится эле-
мент с разделяющим значением 3,такой вид назовем
D
-
последова-
тельностью:
5 4 1 2 3
Прежде чем разделяющее значение 3 окажется на месте разделя-
ющего элемента, произойдет перестановка значений элементов. В ре-
зультате преобразования исходной
D
-
последовательности получается
другая последовательность:
2 1 3 5 4
особенностью которой является то, что она создала две новые
D
-
по-
следовательности. После установки разделяющего элемента 3в новых
подпоследовательностях слева 2, 1 и справа 5, 4 также требуются
максимальные перестановки для установки в них разделяющих эле-
ментов.
D
-
последовательность характеризуется следующими свойствами:
1)
начальная
D
-
последовательность содержит два элемента, упо-
рядоченных в обратном порядке;
2)
при поиске места разделяющего элемента необходимо произве-
сти максимальное число перестановок значений в массиве;
3)
после установки разделяющего элемента правая и левая подпо-
следовательности должны быть
D
-
последовательностями;
4)
равное число элементов в правой и левой подпоследователь-
ностях.
Эти свойства обеспечивают максимальное количество итераций
вечного цикла и хорошо подходят для оценки максимального числа
94
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
