Приклад 1.

Формалізуємо алгоритм сортування методом вставки, а також наведемо його програмну реалізацію. Підмасив, що містить елементи з другого до останнього, вва­жати невідсортованою частиною. Поки ця частина не стане порожньою, викону­вати такі дії.

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.