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

Алгоритм сортировки вставкой или включением подобен упорядочению колоды карт. В процессе сортировки массив разделяется на две части: отсортированную a[1..i-1] и не отсортированную a[i..n]. Поочередно из неупорядоченой части массива выбирается элемент a[i] и вставляется в нужную позицию j упорядоченной части.

В начале работы алгоритма все элементы, за исключением первого, считаются неупорядоченными. Затем с помощью оператора цикла организуется n-1 проход массива:

for i:=2 to n do …

В каждом из этих проходов необходимо осуществлять поиск соответствующей позиции в отсортированной части массива, сдвигать его элементы и в освободившуюся позицию вставить выбранный элемент. Этот внутренний цикл можно организовать так

j:=i;

while (a[j]<a[j-1]) and (j>1) do

begin Swap(a[j],a[j-1]); Dec(j) end;

Можно исключить условие достижения индексом j единицы путем введения фиктивного элемента a[0]=- , т.е. элемента, значение которого меньшего любого элемента массива a[1..n].