операций. Свойство 4 является следствием требования максимального
числа перестановок, которые будет необходимо произвести в новых
подпоследовательностях относительно установленного разделяюще-
го элемента. Из этого также следует, что разделяющий элемент будет
находиться посередине получающейся последовательности. В таблице
представлено несколько
D
-
последовательностей и количество элемен-
тов в них. Интересно отметить, что количество элементов в следую-
щей
D
-
последовательности удваивается, и добавляется один новый
разделяющий элемент.
Таблица
Начальные
D
-
последовательности
Число
элементов
D
-
последовательность
2
2, 1
5
5, 4, 1, 2, 3
11
8, 7, 10, 11, 9, 3, 2, 1, 4, 5, 6
23
17, 16, 13, 14, 15, 21, 23, 22, 19, 20, 18, 6, 5, 4, 1, 2, 3, 9, 11, 10, 7, 8, 12
Для того чтобы экспериментально проверить количество итераций,
в тело вечного цикла включают счетчик
cc
,
а также счетчики индексов
ci
и
с
j
,
как показано ниже:
unsignedint cc = 0, ci = 0, cj = 0;
//
счетчики итераций
while( true )
{
c++;
//
увеличение счетчика
while( a[i]
<
v &&i
<
m ) { ++i; ++ci; }
//
меньший
while( v
<
a[j] && j
>
left ) { –j; ++cj; }
//
больший
if(i
>
= j ) break;
//
обмен не нужен
if( a[i] == a[j] ) break;
//
обмен не нужен
r = a[i];
//
обмен a[i] и a[j]
a[i] = a[j];
a[j] = r;
}
cout
<<
"
n = "
<<
right-left+1;
cout
<<
"
ci = "
<<
ci
<<
"
cj = "
<<
cj
<<
endl;
В распечатке приведены значения счетчиков
cc
,
ci
,
cj
для несколь-
ких
D
-
последовательностей при различном количестве элементов
n
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
95
