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

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

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

Пример реализации:

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

1. Наиболее эффективен для частично отсортированных записей.

2. Число сравнений:

- минимальное – N-1;

- максимальное - N*(N-1)/2.

3. Число перемещений:

- минимальное – 0;

- максимальное - N*(N-1)/2.

4. Не требуется наличие всего набора данных до начала сортировки