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

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

 

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

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

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

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

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

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

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

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

 

 

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

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