Формалізуємо алгоритм сортування методом вставки, а також наведемо його програмну реалізацію. Підмасив, що містить елементи з другого до останнього, вважати невідсортованою частиною. Поки ця частина не стане порожньою, виконувати такі дії.
1. Зберегти перший елемент невідсортованого підмасиву в допоміжній змінній.
2. Визначити позицію вставки збереженого елемента у масив. Для цього дотримуватися перелічених далі вказівок.
2.1.Вважати перший елемент масиву поточним.
2.2.Доки елемент для вставки більше за поточний, збільшувати індекс поточного елемента.
3.Вставити збережений на кроці 1 елемент на знайдену позицію вставки, зсунувши на одну позицію вправо решту відсортованої частини.
4.Пересунути початок невідсортованої частини на одну позицію вправо.
programex6_1; {сортування вставкою}
usescrt;
varn,i,j,k:integer; {кількість та індекси елементів}
а:аrrау[1..10] of integer;
tmp:integer; {елемент, що вставляється у відсортовану частину масиву}
Begin
clrscr;
randomize; {ініціалізувати генератор випадкових чисел}
writeln(‘insertion sort’);
writeln('enter number of the components (<=10)');
readln(n); {ввести кількість елементів масиву}
fori:=1 to n do {генерувати масив}
a[i]:=random(30);
writeln('generated array');
forі:=1 to n do {вивести згенерований масив}
write(a[i].' ');
writeln;
writeln(‘sort process’);
for i:=2 to n do {сортувати методом вставки}
begin {і - початок невідсортованого підмасиву}
tmp:=a[i]; {вибрати елемент для вставки}
j:=l; {цикл пошуку позиції вставки}
while tmp>a[j] do {якщо елемент, що вставляється.}
j:=j+l; {менший або рівний поточному, то j фіксує позицію вставки}
for k:=i-l downto j do {зсунути вправо елементи}
a[k+l]:=a[k]; {невідсортованої частини}
a[j]:=tmp; {вставка вибраного елемента у позицію j}
for k:=l to n do {виведення проміжних результатів}
write(a[k],' ');
writeln;
end;
writeln('sorted array');
for i:=l to n do {виведення відсортованого масиву}
write(a[i],' ');
readln;
End.
