Сортировка включением - вставкой
При сортировке вставкой сначала упорядочиваются два элемента массива. Затем делается вставка третьего элемента в соответствующее место по отношению к первому и второму элементам. Имея уже упорядоченный массив из K элементов, мы добавляем еще один элемент, включая его в массив таким образом, чтобы упорядоченность не нарушилась. Сортировка может производиться одновременно со вводом массива.
Различные методы поиска места для включаемого элемента приводят к различным модификациям сортировки включением.
При использовании линейного поиска вычислительная сложность сортировки вклю-чением составляет O(N*N), а при использовании двоичного поиска- O(N*Log2N) (имеется в виду логарифм по основанию 2).
Пример. Сортировка по возрастанию массива A из N целых чисел включением с линейным поиском.
Различные методы поиска места для включаемого элемента приводят к различным модификациям сортировки включением.
При использовании линейного поиска вычислительная сложность сортировки вклю-чением составляет 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.
