Алгоритм сортировки простыми вставками производится в цикле
j=2,3,...,N. На начальном этапе упорядоченная последовательность
состоит их одного элемента X1. На j-м этапе запись Х(J) вставляется
на свое правильное место среди Х(1), Х(2),..., Х(j-1). При вставке
запись Х(j) временно размещается в запись S и просматриваются записи Х(j-1), Х(j-2),..., Х(1); их ключи сравниваются с ключом T записи S и записи сдвигаются вправо, если обнаруживается, что их ключи больше Т.
Структурограмма алгоритма сортировки методом вставки представлена
на рис.
Пример.
5, 4, 1, 2, 3
J=2, I=1, T=4
5 5 1 2 3
I=0
4 5 1 2 3
J=3, I=2, T=1
4 5 5 2 3
I=1
4 4 5 2 3
I=0
1 4 5 2 3
J=4, I=3, T=2
1 4 5 5 3
I=2
1 4 4 5 3
I=1
1 4 4 5 3
1 2 4 5 3
J=5, I=4, T=3
1 2 4 5 5
I=3
1 2 4 4 5
I=2
1 2 3 4 5
Пример реализации:
procedure SortInsert (var Arr : array of Integer; n : Integer);var i, j, Temp : Integer;begin for i := 1 to n do begin Temp := Arr [i]; j := i - 1; while Temp < Arr [j] do begin Arr [j + 1] := Arr [j]; Dec (j); if j < 0 then Break; end; Arr [j + 1] := Temp; end;end;
Характеристики метода вставки:
1. Наиболее эффективен для частично отсортированных записей.
2. Число сравнений :
- минимальное – N-1;
- максимальное - N*(N-1)/2.
3. Не требуется наличие всего набора данных до начала сортировки
