Масив поділяється на дві частини: відсортовану і не відсортовану. Елементи з не відсортованої частини по черзі вибираються та вставляються в відсортовану частину так, щоб не порушити в ній впорядкованість елементів. На початку роботи алгоритму у відсортованій частині масиву знаходиться тільки один перший елемент, а у не відсортованій частині - всі інші елементи.
Таким чином, алгоритм буде складатися з (n-1) проходу (n- розмірність масиву), кожен з яких буде включати чотири дії:
- взяття чергового i-го не відсортованого елемента та збереження його в додаткової змінній;
- пошук позиції j у відсортованій частині масиву, в якій присутність взятого елемента не порушить впорядкованості елементів;
- зсув елементів масиву від i-1-го до j-го вправо, щоб звільнити знайдену позицію вставки;
- вставка взятого елемента в знайдену j-ю позицію.
Програма, яка реалізує розглянутий алгоритм, буде мати наступний вигляд:
Program Insertionsort;
Var
Vector : array [1..50] of real ;
B : real;
i,j,k,n: integer;
begin
Writeln(' Введіть розмірність масиву: ');
Readln(n);
Writeln(' Введіть елементи масиву: ');
For i:=1 to n do
read (vector[i]);
{-------------Сортування------------- }
for i := 2 n do to
begin
B := vector[i]; {Взяття не відсортованого елемента}
{Цикл пошуку позиції вставки}
j := 1 ;
While ( b >vector[j]) do
j : = j+1; {Після закінчення циклу індекс j фіксує позицію вставки}
{Цикл зміщення елементів для звільнення позиції вставки}
For k : = i-1 downto j do
Vector [k + 1] : = Vector [k];
{Вставка взятого елемента на знайдену позицію}
Vector[j] : = b;
End;
{----------------------------------------------------------------------------}
Writeln (' Відсортований масив: ');
For i : = 1 n do to
Write ( Vector[i] :8:2);
Writeln;
End.
