Помощь - Поиск - Пользователи - Календарь
Полная версия: Quicksort
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
bigformat
Не могу понять,до и после сортировки одно и тоже время....
Код
writeln('Kolichestvo chisel v massive:');
readln(rnd);
for i:=1 to rnd do begin
data[i]:=random(rnd);
end;
writeln('poluchenniy massiv:');
for i:=1 to rnd do begin
write(data[i],' ');
end;
writeln;
begin
gettime(h,m,s,ms);
quicksort(data,1,rnd);
gettime(h1,m1,s1,ms1);
writeln('Otsortirovanniy massiv:');
for i:=1 to rnd do
write(data[i],' ');
writeln('s:',h,':',m,':',s,':',ms);
writeln('e:',h1,':',m1,':',s1,':',ms1);
end;
end.

кто может сказать...еще,как вычислить теперь значение времени,за которое отсортировалось.?
Altair
Просто выполняется сортировка слишком быстро. Прогони ее сотни тысяч раз в цикле, а потом послеченное время подели на кол-во итераций, что бы примерно подсчитать время выполнения сортировки.
klem4
Да ... видимо время работы менее 1 мс, вот тебе на следующий раз модуль для замера времениб чтобы постоянно не юзать gettime

Модуль и пример работы :

Unit XTIMER;

INTERFACE
Var elapsed: Longint; { прошедшее время, в милисекундах. }
Procedure ClockOn;    { включает счётчик времени }
Procedure ClockOff;   { выключает его }
Procedure PrintTime;  { выводит прошедшее время }

IMPLEMENTATION

{uses CRT;}
const Seg0040: word=$0040; { constant of CRT module }

var start:longint;

{ Copyright (c) 1989-1993 Norbert Juffa }
FUNCTION Clock: LONGINT; ASSEMBLER; { same as VMS; time in milliseconds }
ASM
    PUSH    DS		    { save caller's data segment }
    MOV     DS, Seg0040     { access ticker counter }
    MOV     BX, 6Ch	    { offset of ticker counter in segm.}
    MOV     DX, 43h	    { timer chip control port }
    MOV     AL, 4	    { freeze timer 0 }
    PUSHF		    { save caller's int flag setting }
    CLI 		    { make reading counter an atomic operation}
    MOV     DI, DS:[BX]     { read BIOS ticker counter }
    MOV     CX, DS:[BX+2]
    STI 		    { enable update of ticker counter }
    OUT     DX, AL	    { latch timer 0 }
    CLI 		    { make reading counter an atomic operation}
    MOV     SI, DS:[BX]     { read BIOS ticker counter }
    MOV     BX, DS:[BX+2]
    IN	    AL, 40h	    { read latched timer 0 lo-byte }
    MOV     AH, AL	    { save lo-byte }
    IN	    AL, 40h	    { read latched timer 0 hi-byte }
    POPF		    { restore caller's int flag }
    XCHG    AL, AH	    { correct order of hi and lo }
    CMP     DI, SI	    { ticker counter updated ? }
    JE	    @no_update	    { no }
    OR	    AX, AX	    { update before timer freeze ? }
    JNS     @no_update	    { no }
    MOV     DI, SI	    { use second }
    MOV     CX, BX	    {  ticker counter }
@no_update:  NOT     AX 	     { counter counts down }
    MOV     BX, 36EDh	    { load multiplier }
    MUL     BX		    { W1 * M }
    MOV     SI, DX	    { save W1 * M (hi) }
    MOV     AX, BX	    { get M }
    MUL     DI		    { W2 * M }
    XCHG    BX, AX	    { AX = M, BX = W2 * M (lo) }
    MOV     DI, DX	    { DI = W2 * M (hi) }
    ADD     BX, SI	    { accumulate }
    ADC     DI, 0	    {  result }
    XOR     SI, SI	    { load zero }
    MUL     CX		    { W3 * M }
    ADD     AX, DI	    { accumulate }
    ADC     DX, SI	    {  result in DX:AX:BX }
    MOV     DH, DL	    { move result }
    MOV     DL, AH	    {  from DL:AX:BX }
    MOV     AH, AL	    {	to }
    MOV     AL, BH	    {	 DX:AX:BH }
    MOV     DI, DX	    { save result }
    MOV     CX, AX	    {  in DI:CX }
    MOV     AX, 25110	    { calculate correction }
    MUL     DX		    {  factor }
    SUB     CX, DX	    { subtract correction }
    SBB     DI, SI	    {  factor }
    XCHG    AX, CX	    { result back }
    MOV     DX, DI	    {  to DX:AX }
    POP     DS		    { restore caller's data segment }
END

procedure clockon;
begin
	start:=clock;
end;
procedure clockoff;
begin
	elapsed:=clock-start;
end;
Procedure PrintTime;
begin
	writeln('Elapsed time = ',elapsed, ' ms');
end;

BEGIN
	Port [$43] := $34;  { need rate generator, not square wave }
	Port [$40] := 0;    { generator as programmed by some BIOSes }
	Port [$40] := 0;    { for timer 0 }
END.



uses xtimer;
var
   i : integer;
begin
   i := 1;
   ClockOn;
   repeat
      inc(i);
   until i = 1000;
   ClockOff;
   PrintTime;
   readln;
end.
bigformat
кто может подсказать еще насчет геттайма...Как вычислить значение времени,за которое совершена сортировка,имея 2 отрезка времени(начало и конец)...не вычитать же?(что собсно говоря сойдет,если у вас быстрый комп(тк...несколько мс выполняется,и можно просто мс-ды вычесть)
klem4
Цитата
не вычитать же?


Почему нет ?! blink.gif Посчитал на одном отрезке, закомнил, посчитал на втором, прибавил, лишний байт для переменной жалко ? Ну или парочку lol.gif
bigformat
Цитата(klem4 @ 11.01.2006 21:01) *

Почему нет ?! blink.gif Посчитал на одном отрезке, закомнил, посчитал на втором, прибавил, лишний байт для переменной жалко ? Ну или парочку lol.gif

Ну а все же....Ну это у меня дома даже 19к сортируется,бывает меньшьше чем за 1мс,а если я приду к своей преподавательнице,и у меня там секунд 5 он сортировать будет...
volvo
Function GetTime: LongInt;
Var h, m, s, ms: Word;
begin
  Dos.GetTime(h, m, s, ms);
  GetTime := ms + 100 * (s + 60 * (m + 60 * h));
end;

...
start := GetTime;
  { твоя сортировка }
WriteLn('Время сортировки = ', GetTime - start);
...
bigformat
respect volvo,оч помог.
на будущее,кто будет искать...или кому лень будет
Код

program Kviksort;
uses crt,dos;
const n=20000;
type
list=array[1..n] of integer;
var
data:list;
i,rnd: integer;
start:word;

function Gettime:LongInt;
var h,m,s,ms:word;
begin
dos.gettime(h,m,s,ms);
gettime:=ms+100*(s+60*(m+60*h));
end;

procedure quicksort(var a:list; min,max: integer);
procedure sort(l,r: integer);
var
i,j,x,y: integer;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]<x do
i:=i+1;
while x<a[j] do
j:=j-1;
if i<=j then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
i:=i+1;
j:=j-1;
end;
until i>j;
If l<j then sort(l,j);
If i<r then sort(i,r);
end;
begin
sort(min,max);
end;
begin
randomize;
writeln;
writeln('Kolichestvo chisel v massive:');
readln(rnd);
for i:=1 to rnd do begin
data[i]:=random(rnd);
end;
writeln('poluchenniy massiv:');
for i:=1 to rnd do begin
write(data[i],' ');
end;
writeln;
begin
gettime;
start:=gettime;
quicksort(data,1,rnd);
writeln('Otsortirovanniy massiv:');
for i:=1 to rnd do
write(data[i],' ');
writeln;
write('vremya sortirovki=',gettime-start,'ms');
end;
end.

принимайте какой есть
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.