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

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

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


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

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

Практична робота 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.
Немає коментарів:
Дописати коментар