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

СОРТУВАННЯ МЕТОДОМ ВИБОРУ

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

Завдання 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 hoor(a,b: integer; var m: vector); { Рекурсивний алгоритм швидкого сортування Хоора}

var   i,j,c: integer;     k: real;

begin  if a<b then begin  c:=(a+b) div 2; k:=m[c];{Обираємо ключовий елемент}

        { ділимо масив на дві групи, порівнюючи з ключовим елементом }

    i:=a; j:=b; repeat  if (i=c) and (i<j) then begin swap(m[i],m[j]); c:=j end;

      if   not less(k,m[i])   then   i:=i+1    else  begin  swap(m[i],m[j]);       j:=j-1;

         if j=c then c:=i         end       until i>j;

    { Якщо друга група порожня – перносимо в неї ключовий елемент }

    if   i>b   then   i:=b;        if   trace   then   writevector(b,m);

  {виконуємо сортування кожної частини, викликаючи саму себе процедури}

    hoor(a,i-1,m);        hoor(i,b,m);     end;   end;

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

var    n,i: integer;   m: vector;  ans: char;   {назва змінних величин}

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

 write('Введено розмір масиву(від 1 до ', maxcnt, '): '); n:=2+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;

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

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

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