I,j,k: longint;
X,y: single;
begin
nMove:=0;
nCompare:=0;
for i:=1 to nCurr-1 do
begin
k:=i; x:=A[k];
nMove:=nMove+1;
for j:=i+1 to nCurr do
begin
nCompare:=nCompare+1;
if A[j]<x then
begin
k:=j; x:=A[k];
nMove:=nMove+1;
end;
end;
// A[k]:=A[i];
y:=A[i];
A[k]:=y;
A[i]:=x;
nMove:=nMove+3;
end;
end;
procedure BubbleSort;
var
I,j,k: longint;
X,y: single;
bWas: boolean;
begin
nMove:=0;
nCompare:=0;
for i:=2 to nCurr do
begin
for j:=nCurr downto i do
begin
x:=A[j-1];
y:= A[j];
nMove := nMove + 2;
nCompare := nCompare + 1;
if x>y then
begin
A[j-1]:=y;
A[j]:=x;
nMove := nMove + 2;
end;
end;
end;
end;
begin
nCurr:=1000;
n2:=nCurr;
M2:=0; c:=0; b:=0;
for k:=1 to 12 do
begin
nCurr:=nCurr*2;
FillArray;
IsArraySorted;
// iSortType:=iInsertSort;
iSortType:=iBubbleSort;
case iSortType of
iInsertSort:
InsertSort;
iBubbleSort:
BubbleSort;
iStraightSelectionSort:
StraightSelectionSort;
end;
IsArraySorted;
if k>2 then
begin
b:=ln(M2/M1)/ln(n2/n1);
c:=M1/exp(b*ln(n1));
writeln('nCurr=',nCurr, ' nMove=',nMove:0,' c=',c:0:8,' b=',b:0:8);
end;
if iSortType=iStraightSelectionSort then
begin
pOur:=M2/(n2*ln(n2)+n2*(2+EulerGamma)+
ln(n2)+(EulerGamma-3.5)+5/(12*n2));
pVirt:=M2/(n2*ln(n2)+n2*EulerGamma);
writeln(' pOur=',pOur:0:8,' pVirt=',pVirt:0:8);
end;
n1:=n2; n2:=nCurr;
M1:=M2; M2:=nMove;
end;
writeln('Finish!');
readln;
end.
Результат для числа переносов при сортировке методом прямого выбора проверяется с помощью отношения
,
где
оценивается по формулам (2) и (3). Обе
формулы должны обеспечивать тенденцию
,
однако (3) в этом смысле выглядит
неубедительно (см. рисунок).
