1. Основные понятия алгоритмизации и программирования

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

Рассмотрим процесс сортировки методом вставки (прямого включения) массива а[1], а[2], ..., a[n]. Вначале в исходном массиве выделяется уже отсортированная, например по неубыванию, часть а[1] ≤ а[2] ≤...≤ а[i-1] и не отсортированная a[i], a[i+l],..., a[n]. Затем с шагом 1, начиная с i = 2 чередуя сравнения и перемещения элемента a[i], в отсортированной части массива определяется такой индекс (ключ) j (1 ≤ j ≤ i -1), чтобы выполнялись неравенства a[j-l] ≤ a[i] ≤ a[j]. Если такой индекс найден, то элемент a[i] вставляется на соответствующее место. Для этого выполняется сдвиг на одну позицию вправо элементов отсортированной части: a[j], …, а[i-1]. После этого осуществляется переход к следующему значению i. В противном случае просто происходит переход к следующему значению i. С каждым шагом отсортированная часть массива увеличивается на один элемент. Очевидно, что для выполнения полной сортировки потребуется n -1 шаг, где n - число элементов исходного массива.
Покажем процесс сортировки вставками на примере целочисленного массива а[1..12], состоящего из чисел 22, -14, 13, 28, 6, 41, -5, 18, 0, 35, 6,-15 (значком * обозначены вставленные элементы, выделены элементы отсортированной части)

Исходный массив:	22	-14	13	28	6	41	-5	18	0	35	6	-15
1-й шаг