неділя, 18 березня 2018 р.

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


Практична робота 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*log2(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.

Немає коментарів:

Дописати коментар