А.Ф. Деон, Ю.И. Терентьев
2
исходного массива в виде упорядоченной части
a
[0],
a
[1],
a
[2] и
неупорядоченной —
a
[3],
a
[4], …,
a
[
n
–1]. Продолжая итерации для
начальных элементов всех неупорядоченных частей, получаем отсор-
тированный массив
a
. Функция, реализующая метод последователь-
ной вставки, имеет следующий вид:
void SortInsertSeq( int a[], const int n )
{
for( int j = 1; j < n; j++ ) // цикл исходных элементов
{
if( a[j-1] <= a[j] ) continue; // вставка не нужна
for( i = j-1; i >=0; i-- ) // поиск места вставки
if( a[i] < a[j] ) break; // перед местом вставки
i++; // место вставки
int r = a[j]; // запомнить вставляемый элемент
for( int m = j; m > i; m-- ) a[m] = a[m-1]; // сдвиг
a[i] = r; // расположить вставляемый элемент
}
}
Скоростные свойства функции
SortInsertSeq()
определяются ко-
личеством выполненных операций в теле функции [2]. На первом
этапе выполняется внешний цикл для правой неупорядоченной части
массива. В заголовке цикла
for
(
int j =
1
; j < n; j++
) до начала
итераций настраиваются две операции: 1) установка начального
значения
int j =
1; 2) начальная проверка условия
j < n
. Обозначим
это количество как
1,1
2
W
=
.
Кроме того, на каждой итерации внешнего цикла в заголовке
цикла выполняется одна операция на очередную проверку окончания
цикла
j < n
и две операции на увеличение переменной цикла
j++
:
(
)
(
)
1
1,2
1
1 2 3 1
n
j
W
n
−
=
= + = −
∑
.
Всего на первом этапе выполняется следующее количество опе-
раций:
(
)
1
1,1 1,2
2 3 1 3 1
W W W n
n
= + = + − = −
.
На втором этапе выполняется проверка на необходимость встав-
ки с помощью инструкции условия
if
(
a
[
j
–1]
< a
[
j
])
continue
. На
каждой итерации внешнего цикла по индексу
j
будет выполнено
четыре операции на проверку условия
a
[
j
–1]
< a
[
j
]:
