Препод сказал что нужно сделать тоже самое и для улучшенных методов.
uses crt;
const n=15;
var
a:array [1..n] of integer;
b:array [1..n] of integer;
peres,srav:longint;
i:integer;
otv:char;
procedure menu;
begin
writeln('1-Puzyrek');
writeln;
writeln('2-Vstavka');
writeln;
writeln('3-Vybor');
writeln;
writeln('4-Shell');
writeln;
writeln('5-Bystraya sortirovka');
writeln;
writeln('6-Piramida');
writeln;
writeln('7-Sozdat massiv');
writeln;
writeln('8-Exit');
writeln;
otv:=readkey;
end;
procedure vyvod;
begin
writeln('Ishodnyj massiv');
writeln;
for i:=1 to n do
write(' ',b[i]);
writeln;
writeln;
writeln('Posle sortirovki');
writeln;
for i:=1 to n do
write(' ',a[i]);
writeln;
writeln;
end;
function sravnenie(a, b: integer): boolean;
begin
inc(srav);
sravnenie := a < b;
end;
procedure sozd_mas;
var i:integer;
begin
writeln('vvedite elem mas');
for i:=1 to n do
readln(b[i]);
writeln('Massiv sozdan');
writeln;
end;
procedure puzyr;
var i,j,temp:integer;
begin
writeln;
writeln(' METOD ny3bIpbKA ');
writeln;
peres:=0;
srav:=0;
for i:=1 to n do
a[i]:=b[i];
for i := 2 to n do
begin
for j:=n downto i do
begin
inc(srav);
if a[j-1] > a[j] then
begin
temp := a[j-1];
a[j-1] := a[j];
a[j] := temp;
inc(peres);
end;
end;
end;
vyvod;
writeln('Chislo perestanovok = ',peres);
writeln('Chislo sravneniy = ',srav);
writeln;
readln;
end;
procedure vstavka;
var i,j,temp:integer;
begin
writeln;
writeln(' METOD BCTABOK');
writeln;
peres:=0;
srav:=0;
for i:=1 to n do
a[i]:=b[i];
for i:=2 to n do
begin
temp:=a[i];
j:=i-1;
While (j>0) and (sravnenie(temp, a[j])) do
begin
a[j+1]:=a[j];
dec(j);
inc(peres);
end;
a[j+1]:=temp;
end;
vyvod;
writeln('Chislo perestanovok = ',peres);
writeln('Chislo sravneniy = ',srav);
writeln;
readln;
end;
procedure vybor;
var i,j,k,temp:integer;
begin
writeln;
writeln('METOD BbI6OPA');
writeln;
peres:=0;
srav:=0;
for i:=1 to n do
a[i]:=b[i];
for i:=1 to n-1 do
begin
k:=i;
temp:=a[i];
for j:=i+1 to n do
begin
inc(srav);
if a[j]<temp then
begin
k:=j;
temp:=a[j];
end;
end;
a[k]:=a[i];
if k<>i then inc(peres);
a [i]:=temp;
end;
vyvod;
writeln('Chislo perestanovok = ',peres);
writeln('Chislo sravneniy = ',srav);
writeln;
readln;
end;
procedure Shell;
var h:array [1..n] of integer;
t,m,i,j,k,temp:integer;
begin
writeln;
writeln(' METOD Shella ');
writeln;
peres:=0;
srav:=0;
for i:=1 to n do
a[i]:=b[i];
write('Chislo shagov: ');
readln(t);
for i:=1 to t do
begin
write(i,'-y shag = ');
readln(h[i]);
end;
for m:=1 to t do
begin
k:=h[m];
for i:=k+1 to n do
begin
temp:=a[i];
j:=i-k;
while (j>0) and (temp<a[j]) do
begin
a[j+k]:=a[j];
dec(j,k);
inc(srav);
end;
a[j+k]:=temp;
inc(peres);
end;
end;
vyvod;
writeln('Chislo perestanovok = ',peres);
writeln('Chislo sravneniy = ',srav);
writeln;
readln;
end;
Procedure QuickSort(left,right:integer);
var i,j:integer;
sred,temp:integer;
begin
i:=left;
j:=right;
sred:=a[(left+right) div 2];
repeat
while (a[i]<sred) do
begin
inc(i);
inc(srav);
end;
while (a[j]>sred) do
begin
dec(j);
inc(srav);
end;
if i<=j then
begin
temp:=a[i];
a[i]:=a[j];
a[j]:=temp;
inc(i);
dec(j);
inc(srav);
end;
until i>j;
if left<j then
begin
inc(peres);
QuickSort(left,j);
end;
if i<right then
begin
inc(peres);
QuickSort(i,right);
end;
end;
Procedure Sito(al,ar:word);
var i,j,x:integer;
begin
i:=al;
j:=2*al;
x:=a[al];
inc(srav);
if (j<ar) and (a[j+1]>a[j]) then inc(j);
while (j<=ar) and (a[j]>x) do
begin
a[i]:=a[j];
i:=j;
j:=2*j;
inc(srav);
inc(peres);
if (j<ar) and (a[j+1]>a[j]) then
begin
inc(j);
inc(srav);;
end;
end;
a[i]:=x;
end;
procedure piramida;
var left,right,temp:integer;
begin
left:=(n div 2)+1;
right:=n;
while left>1 do
begin
left:=left-1;
Sito(left,right);
end;
while right>1 do
begin
temp:=a[1];
inc(srav);
inc(peres);
a[1]:=a[right];
a[right]:=temp;
right:=right-1;
Sito(left,right);
end;
end;
begin
clrscr;
randomize;
repeat
begin
menu;
case otv of
'1':puzyr;
'2':vstavka;
'3':vybor;
'4':Shell;
'5':begin
writeln;
writeln(' METOD Bystroy sortirovki ');
writeln;
peres:=0;
srav:=0;
for i:=1 to n do
a[i]:=b[i];
QuickSort(1,n);
vyvod;
writeln('Chislo perestanovok = ',peres);
writeln('Chislo sravneniy = ',srav-1);
writeln;
readln;
end;
'6':begin
writeln;
writeln('Piramidalnaya sortirovka');
writeln;
peres:=0;
srav:=0;
for i:=1 to n do
a[i]:=b[i];
piramida;
vyvod;
writeln('Chislo perestanovok = ',peres);
writeln('Chislo sravneniy = ',srav);
writeln;
readln;
end;
'7':sozd_mas;
'8':end;
end;
until otv='8';
end.
Исходный массив для метода Шелла: 15 33 42 7 12 19. 2 шага шруппировки: 3 и 1. должно быть 8 сравнений и 5 перестановок.
Для быстрой сортировки: 13 42 28 17 9 25 47 31 39 15 20. 22 сравнения и 6 перестановок. Считает все правильно но может быть результаты подогнаны?
Для пирамидалььной сортировки: 45 40 28 25 30 44 33 22 60 15 55 47 66 20 50. 73 сравнения и 49 перестановок.
Помогите пожалуйста посчитать сравнения и перестановки. Заранее спасибо
Правила форума
Прочтите прежде чем задавать вопрос!
