Простая вставка

Сортировка вставками

При сортировке вставками записи просматриваются по одной и

каждая новая запись вставляется на надлежащее место среди ранее

упорядоченных записей.

Известны следующие методы сортировки вставками: простая

вставка, бинарная вставка, метод Шелла и др., различающиеся

способами поиска подходящего места для вставки элемента.

Все записи условно разделяются на две части - упорядоченную

и исходную (неупорядоченную).

Алгоритм сортировки простыми вставками производится в цикле

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. Не требуется наличие всего набора данных до начала сортировки