Позиции, в которую должен быть включен

элемент a[i]}

end;

a[j+1]: =x {включение a[i] в «дырку» в левой

части}

еnd

END;

Сложность:

Количество элементарных операций зависит, в первую очередь, от размера сортируемого массива. Однако величина n не определяет это количество однозначно. Для различных массивов одного и того же размера тело цикла While x.key< a[j].key Do будет выполняться различное число раз. Поэтому необходимы три оценки сложности: минимальная, максимальная и средняя.

Минимальная сложность получается в том случае, когда элементы упорядочиваемого массива уже располагаются в нужном порядке. Тогда проверки x.key< a[j].key всегда будут давать отрицательный результат и тело цикла не выполнится ни разу. И выполнение процедуры сведется к выполнению следующих операторов:

For i: =2 To n Dobеgin

x: =a[i];

a[0]: =x;

j: =i-1;

а[j+1]: =x

еnd

Тело цикла For исполняется точно n-1 раз, и число пересылок записей (присваиваний): M_min=3(n-1).

Число сравнений ключей: C_min=n-1.

Максимальная сложность получается в том случае, когда элементы исходного массива расположены в порядке убывания. Тело цикла While выполняется до тех пор, пока элемент х не натолкнется на барьер, т.е. при i =2 один раз, при i =3 два раза; при i=n выполнится (n-1) раз.

Количество пересылок записей: M_max=3(n-1)+ =

=3(n-1)+(1+2+...+n-1)=3(n-1)+n(n-1)/2=(6n-6+n²-n)/2=

=(n²+5n-6)/2.

Количество сравнений: C_mах=2+3+…+n=(n+2)(n-1)/2=

=(n²-n+2n-2)/2=(n²+n-2)/2.

Средняя оценка сложности получится, если предположить, что все элементы исходного массива – случайные числа. Результат очередной проверки в операторе While также является случайным, т.е. не можем сказать, сколько раз выполнится тело цикла.

Структуру процедуры с точки зрения анализа сложности можно переписать так:

For i: =2 To n Do

begin