Сортировка вставками (метод прямого включения)

1) Начиная со 2-го элемента, каждый текущий элемент с номером i запоминается в промежуточной переменной.

2) Затем просматриваются предыдущие i –1 элемент и ищется место вставки i-го элемента таким образом, чтобы не нарушить упорядоченности, при этом все элементы, превышающие i - й, сдвигаются вправо.

3) На освободившееся место вставляется i -й элемент.

Таблица 2. Пример сортировки прямыми включениями.

i=2	5
i =3	4
i =4	3
Отсортированный массив

Программа сортировки вставками:

void sort_insert (int *m, int n)

{

int j, r;

for (int i=1; i< n; i++)

{

r=m[i]; // Запоминаем текущий элемент в промежуточной переменной

j=i-1;

while (j> =0 & & m[j]> r) // Ищем новое место вставки,

{ m[j+1]=m[j]; j--; } // сдвигая на 1 элемент вправо

m[j+1]=r; // На освободившееся место вставляется элемент

}

}