Цитата(northener @ 23.4.2012, 00:40  ) | | Заноза сравнительно легко извлекается путём вычисления "среднего" времени выполнения алгоритма при измерении нескольких вызовов вышеупомянутого. |
Т.е. для одного и того же N несколько раз замерять, а потом среднее арифиметическое вычислять? Чтож, подумаю.
Пока препод в коммандировке выкладываю код. Чуть позже доработаю ещё с учётом данных советов.
| Код |
program Project1;
{$APPTYPE CONSOLE}
uses
SysUtils,
windows;
const n=10000;
type
mas1=array[1..n] of integer;
mas2=array[1..n*n] of integer;
var a:mas1;
var ft : text;
WaitCal: Int64;
Start, Finish: Int64;
procedure Wait(ns: Integer);
var
Counter, Freq, WaitUntil: Int64;
begin
if QueryPerformanceCounter(Counter) then
begin
QueryPerformanceFrequency(Freq);
WaitUntil := Counter + WaitCal + (ns * (Freq div 1000000));
while Counter < WaitUntil do
QueryPerformanceCounter(Counter);
end
else
Sleep(ns div 1000);
end;
procedure prosmotr(a:mas1);
var
i: Integer;
begin
for i := 1 to 10 do
write(' ',a[i]);
writeln;
end;
{ Заполнение массива числами по возрастанию }
procedure FillInc( var A : mas1);
var
i : longint;
begin
for i := 1 to n do
A[i] := i;
end;
{ Заполнение массива числами по убыванию }
procedure FillDec( var A : mas1);
var
i : longint;
begin
for i := 1 to n do
A[i] := n-i;
end;
{ Заполнение массива случайными числами }
procedure FillRand( var A : mas1);
var
i :longint;
begin
randomize;
for i := 1 to n do
begin
A[i] := random(21) mod n;
end;
end;
{Сортировка пузырьком}
procedure sortbuble(a:mas1; t:longint);
var i,j:integer;
tmp:integer;
begin
QueryPerformanceCounter(Start);
for i:=1 to t-1 do
for j:=i+1 to t do
if A[i] >= A[j] then begin
tmp := A[i];
A[i] := A[j];
A[j] := tmp;
end;
QueryPerformanceCounter(Finish);
writeln(ft, t,';',Finish-Start);
writeln;
end;
{Сортировка Шелла}
procedure shell_sort(a:mas1; var v:longint);
var ii, m, x, s, p, t, k, r, i, j : Integer;
begin
QueryPerformanceCounter(Start);
t := Trunc(Ln(n) / Ln(2));
repeat
t := t - 1;
k := (1 shl t) - 1;
p := v mod k;
s := v div k;
if p = 0 then
p := k
else
s := s + 1;
for i := 1 to k do {берём и длинные, и короткие подпоследовательности}
begin
if i = p + 1 then
s := s - 1; {для коротких — уменьшаем длину}
for j := 1 to s - 1 do {метод ПрВст с шагом k}
if a[i + (j - 1) * k] > a[i + j * k] then
begin
x := a[i + j * k];
m := i + (j - 1) * k;
while (m > 0) and (a[m] > x) do
begin
a[m + k] := a[m];
m := m - k;
end;
a[m + k] := x;
end;
end;
until k = 1;
QueryPerformanceCounter(Finish);
writeln(ft, v,';',Finish-Start);
end;
var i:longint;
begin
assign(ft, 'log.txt');
append(ft);
writeln('Sravnenie pusirka i shella');
writeln(ft,'uporyad');
FillRand(a);
write('UCX:');
prosmotr(a);
write(ft,'sortirovka pusirkom ');
for i := 1 to 10000 do begin
sortbuble(a,i);
end;
write(ft,'Shell');
for i := 1 to 10000 do begin
shell_sort(a,i);
end;
writeln;
writeln('RANDOM');
writeln(ft,'RANDOM');
FillRand(a);
write('UCX:');
prosmotr(a);
write(ft,'sortirovka pusirkom ');
for i := 1 to 10000 do begin
sortbuble(a,i);
end;
writeln(ft,'Shell');
for i := 1 to 10000 do begin
shell_sort(a,i);
end;
writeln(ft,'Ubivanie');
FillDec(a);
write('UCX:');
prosmotr(a);
write(ft,'sortirovka pusirkom ');
for i := 1 to 10000 do begin
sortbuble(a,i);
end;
writeln(ft,'Shell');
for i := 1 to 10000 do begin
shell_sort(a,i);
end;
write('GOTOVO');
readln;
end.
|
UPD:Ничего не потребовалось редактировать, приняли так. Всем спасибо за помощь. |