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

СОРТУВАННЯ ЕЛЕМЕНТІВ У МАСИВАХ








СОРТУВАННЯ  МЕТОДОМ ПІДРАХУНКУ





ПОРОЗРЯДНЕ СОРТУВАННЯ ЧИСЕЛ

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

Завдання 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 pyramidal(n: integer; var m: vector);

label 1,2;  var i,j,k,l: integer;    v: real;    begin    { Перший етап: побудова піраміди }

  if trace then writeln('Перший етап');    for i:=2 to n do begin     j:=i;

repeat  k:=j div 2;  if less(m[k],m[j]) then swap(m[k],m[j])   else goto 1;    j:=k

    until j=1;  { Тепер виконується умова m[i/2]>=m[i] для будь-якого  i>1 }

  1: if trace then writevector(n,m);   end;  2 етап: вилучаємо з піраміди вершину і в кінець масиву}

   if trace then writeln('Другий етап');     for i:=n downto 2 do begin     v:=m[1];

    j:=1;     while 2*j<i do begin   k:=2*j;

      if less(m[k],m[k+1]) then begin          m[j]:=m[k+1];     j:=k+1;

end else begin m[j]:=m[k];  j:=k;   end;   swpcnt:=swpcnt+1;  end;   m[j]:=m[i];

    if 2*j>i then        while j>1 do begin  l:=j div 2;

         if less(m[j],m[l]) then goto 2;          swap(m[l],m[j]);           j:=l;     end;

    2: m[i]:=v; swpcnt:=swpcnt+1;     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;

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

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

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