Пример выполнения метода

12

10

14

11

17

15

J=2

10<12:

10 12 14 11 17 15

11

Шаг 3, 4:

10	12	14	11	17	15	14>12, перестановки не нужны
10	12	14	11	17	15

11<14, сдвигаем 14 вправо:

10 12 14 14 17 15

11<12, сдвигаем 12 вправо:

10	12	12	14	17	15
		11>10, выполняем вставку:
10	11	12	14	17	15	12

Алгоритм сортировки методом вставки

Формальные параметры процедуры сортировки:

T – имя таблицы;

n – ее размер (количество записей).

13

Алгоритм сортировки

for j:=2 to n do

if t[j].ключ<t[j-1].ключ then begin

zap:=t[j]; i:=j-1; while(i>=1)and

(t[i].key>temp.key) do

begin

t[i+1]:=t[i]; i:=i-1;

	end;
	t[i+1]:=zap;
end;	14

Характеристики метода

Количество операций сравнения:

C = n (n – 1)/4

(при достаточно большом n C = n2/4). Максимальное количество перестановок :

Р ~ n2/4.

15