Пример выполнения расчетов по практическому занятию

Задание: Написать программу реализации алгоритма пузырьковой сортировки для АТД «Очередь» (очередь с одной головой).

Решение:

type ochered=^Rec;

Rec=record

info: integer;

next: ochered;

end;

var

head, head1: ochered;

n, i, j, z, k, y, x, x1: integer;

nop:real;

procedure push(var head:ochered; x:integer); // 6

var a: ochered;

begin

new(a); //+1

a^.info:=x; //+2

a^.next:=head; //+2

head:=a; //+1

end;

procedure pop(var head:ochered; var x:integer); //8+

var a, p: ochered;

begin

a:=head; p:=head; //+2

while a^.next<>nil do begin //+2

p:=a; a:=a^.next; //+3

end;

x:=a^.info; p^.next:=nil; //+4

dispose(a); //+1

end;

function empty(head:ochered): boolean; //2

begin

empty:=head=nil; //+2

end;

procedure iniz(var head:ochered; var n:integer); //1+

var x, i: integer;

begin

for i:= 1 to n do begin

x:=Random(501)+300; //+3

push(head,x); //+6

end;

end;

BEGIN

n:=10;

head:=nil;

iniz(head,n);

head1:=nil;

For i:= 1 to n-1 do

For j:= n downto i+1 do begin

if not empty(head1) then begin //+3

head:=head1; //+1

head1:=nil; //+1

end;

For z:=1 to j-2 do begin //1+

pop(head,y); push(head1,y);//+6+8+

end;

pop(head,x); pop(head,x1); // 16+2*

If x>x1 then begin //+1

push(head1,x); push(head1,x1);end //+12

else begin

push(head1,x1); push(head1,x);end; //+12

If j<n then begin //+1

For k:= 1 to n-j do begin //1+

pop(head,y); push(head1,y); //+6+8

end;

end;

end;

For i:= 1 to n do begin

pop(head1,x);

writeln(x);

end;

readln;

END.

F(n)=1+

+ +

=1+ =

=1+ =

=1+ = 1+ =

=1+ = =

=

O(F(n))=10n⁴

Кол-во элементов	F(n)	O(F(n))	Т(n) [сек]	Nop
		1Е+08	0,11
		1,6Е+09	1,297
		8,1Е+09	5,468
		2,56Е+10	15,461
		6,25Е+10	35,906
		1,296Е+11	71,500
		2,401Е+11	128,687
		4,096Е+11	215,172
		6,56Е+11	343,984
		1Е+12	511,172

C1=T(n)/F(n)	C2=T(n)/F(n)	C3=Nop/F(n)	C4=Nop/O(F(n))
0,00000000011017	0,000000011000000	0,130667537	1,30463601
0,0000000000814	0,000000000810625	0,128327068	1,27740763
0,0000000000675	0,000000000675062	0,126879493	1,26829207
0,0000000000611	0,000000000610977	0,126408761	1,26372673
0,0000000000574	0,000000000574496	0,126126600	1,26098509
0,0000000000551	0,000000000551698	0,125938608	1,25915630
0,0000000000536	0,000000000535973	0,125804384	1,25784952
0,0000000000525	0,000000000525322	0,125703746	1,25668692
0,0000000000524	0,000000000524286	0,125625491	1,25651065
0,0000000000511	0,000000000511172	0,125562897	1,25549631