Сортування чисел методом вставки

Практична робота 26.   Сортування  чисел  методом вставки

Завдання 1.Реалізувати алгоритм сортування методом вставки, що використовує чотири допоміжні процедури та функції.

program sorting;                                         { назва  алгоритму }

const maxcnt=5;                                        { назва  постійної довжини масиву  чисел}

type vector=array[1..maxcnt] of real;           {назва динамічного масиву із дійсних чисел  }

var cmpcnt,swpcnt:  integer;                        {назва змінних величин:  цілих чисел }

     trace:  boolean;                                     {назва змінних величин:  логічних (так/ні) }

procedure writevector(n: integer; m: vector);  {допоміжна процедура друкування масиву}

var i: integer;                                                 {назва змінних величин:  цілих чисел }

begin      writeln('   це m[1]  елемент відсортованого рядка' , m[1]:6:2);   {цикл друку}

  for i:=2 to n do writeln('  це m[', i, '] -ий елемент відсортованого рядка ', m[i]:6:2);

  writeln;  end;                           {закінчення процедури друкування елементів масиву }

function   less(a, b: real): boolean;                {допоміжна функція порівняння елементів}

begin       cmpcnt:=cmpcnt+1;                  { неповне розгалуження для  порівняння чисел }        

  If  trace   then  writeln('Порівняння', a:6:2, ' з ', b:6:2);   less:=a<b;  end;

   procedure swap(var a,b:real);                       {допоміжна процедура - обмін елементів }

var c:real;                                              {назва змінних величин:  дійсних  чисел }

begin        swpcnt:=swpcnt+1;      c:=a; a:=b; b:=c    end;  {виконується   обмін елементів }

procedure inserting(n: integer; var m: vector); {Метод вставки, де порівнянь до n*log₂(n) }

var i,a,b,c:integer;     k: real;

begin      for i:=2 to n do begin  { У відсортованій частині  шукаємо місце черг-ого елемента}

  a:=1; b:=i;   k:=m[i];        while a<b do begin  c:=(a+b)div 2;

      if less(k,m[c]) then           while b>c do begin         m[b]:=m[b-1];  b:=b-1;       end

      else a:=c+1    end;     m[a]:=k; swpcnt:=swpcnt+i-a;

    if trace then writevector(n,m);    end;  end;

{Основний алгоритм, який використовує допоміжні алгоритми}

var    n,i: integer;                {назва змінних величин:  цілих  чисел }

          m: vector;                    {назва змінних величин:  масиву  чисел }

         ans: char;                     {назва змінних величин:  буквених символів }

begin

  repeat                               {цикл з післяумовою  для введення довжини масиву   }

    write('Введено розмір масиву(від 1 до ', maxcnt, '): ');

    n:=1+random(5);   writeln('n=', n);      {випадкове  ціле чисел – це довжина масиву}

  until (1<=n) and (n<=maxcnt);                {Умова перевірки закінчення циклу}

  writeln('Введено масив випадкових чисел:');

  for i:=1 to n do  begin              {цикл з лічильником  для введення елементів масиву }

    m[i]:=2+random(159);  writeln('Введено  випадковe число:', m[i]);

  writeln;   end;                  {цикл з лічильником  для виведення елементів масиву }

  write('Показати процес роботи? (y/N) '); readln(ans);            {діалог з користувачем}

   trace:=(ans='y')or(ans='Y');

  writeln('Обрано метод сортування "ВСТАВКА":');        cmpcnt:=0; swpcnt:=0;

   inserting(n,m); {виклик процедури сортування  методом вставки }

  writeln('Всього виконано ', cmpcnt, ' порівнянь та ', swpcnt, ' перестановок');

  writeln(' Відсортований масив в порядку зростання:');    writevector(n,m);   end.