Сортировка включением - вставкой

При сортировке вставкой сначала упорядочиваются два элемента массива. Затем делается вставка третьего элемента в соответствующее место по отношению к первому и второму элементам. Имея уже упорядоченный массив из K элементов, мы добавляем еще один элемент, включая его в массив таким образом, чтобы упорядоченность не нарушилась. Сортировка может производиться одновременно со вводом массива.

Различные методы поиска места для включаемого элемента приводят к различным модификациям сортировки включением.

При использовании линейного поиска вычислительная сложность сортировки вклю-чением составляет O(N*N), а при использовании двоичного поиска- O(N*Log2N) (имеется в виду логарифм по основанию 2).

Пример. Сортировка по возрастанию массива A из N целых чисел включением с линейным поиском.

program Sort_Include1; 
var A:array[1..100] of integer;
N,i,k,x : integer; 
begin 
 write('количество элементов массива '); 
 read(N); 
 read(A[1]); {for i:=1 to n do read(A[i]);} 
 {k - количество элементов в упорядоченной части массива} 
 for k:=1 to n-1 do 
 begin 
 read(x); {x:=A[k+1];} 
 i:=k; 
 while (i>0)and(A[i]>x) do 
 begin 
 A[i+1]:=A[i]; 
 i:=i-1; 
 end; 
 A[i+1]:=x; 
 end; 
 for i:=1 to n do write(A[i],' '); {упорядоченный массив} 
end.

Пример. Сортировка по возрастанию массива A из N целых чисел включением с двоичным поиском.

program Sort_Include2; 

var A:array[1..100] of integer; 
 N,i,k,x,c,left,right : integer; 

begin 
 write('количество элементов массива '); read(N); 
 read(A[1]); {for i:=1 to n do read(A[i]);} 
 {k - количество элементов в упорядоченной части массива} 
 for k:=1 to n-1 do 
 begin 
 read(x); {x:=A[k+1];} 
 left:=1; right:=k; 
 {левая и правая граница фрагмента для поиска} 
 while left=A[c] then left:=c 
 {берем правую половину с серединой} 
 else right:=c-1; {берем левую половину без середины} 
 end; 
 if x>=A[left] then left:=left+1; 
 {сдвигаем на 1 вправо часть массива, освобождая место для включения x}
 for i:=k downto left do A[i+1]:=A[i]; 
 A[left]:=x; 
 end; 
 for i:=1 to n do write(A[i],' '); {упорядоченный массив} 
end.