[Pascal] Algorytmy sortujące i pobieranie czasu


(Ziem) #1

Witam!

Mam problem/pytanie.

W jaki sposób mogę pobrać czas? Znalazłem funkcję Gettime, ale jest ona mało dokładna.

Przykład (zwraca 0 sekund):

program heap;

uses dos;

const N = 30000;

var

xx:integer;

d: array[1..N] of integer;

h,m,s,s100,start,finish,delta: word;

procedure QuickSort(lewy, prawy : integer);

var

  i,j : integer;

  piwot,x : int64;

begin

  i := (lewy + prawy) div 2;

  piwot := d[i]; d[i] := d[prawy];

  j := lewy;

  for i := lewy to prawy - 1 do

    if d[i] < piwot then

    begin

      x := d[i]; d[i] := d[j]; d[j] := x;

      inc(j);

    end;

  d[prawy] := d[j]; d[j] := piwot;

  if lewy < j - 1 then QuickSort(lewy, j - 1);

  if j + 1 < prawy then QuickSort(j + 1, prawy);

end;


begin

randomize;

for xx :=1 to N do

        d[xx] := random(1000);

        writeln('asdadsa');

        GetTime(h,m,s,s100);

start := 3600*h+60*m+s;

QuickSort(1,N);

GetTime(h,m,s,s100);

finish := 3600*h+60*m+s;

delta := finish - start;

for xx :=1 to N do

        writeln(d[xx]);

writeln('time: ', delta);

readln;

end.

Drugi problem to błąd wyskakujący przy kompilacji algorytmu "sortowanie przez kopcowanie". Podczas wykonywania programu dostaję exitcode 216. Jak tego uniknąć? Kod źródłowy:

program heap;

uses dos;

const N = 30000;

var

xx:integer;

d: array[1..N] of integer;

procedure HeapSort;

var

  i,j,k,m : integer;

  x : int64;

begin

  for i := 2 to N do

  begin

    j := i; k := j div 2;

    x := d[i];

    while (k > 0) and (d[k] < x) do

    begin

      d[j] := d[k];

      j := k; k := j div 2;

    end;

    d[j] := x;

  end;

  for i := N downto 2 do

  begin

    x := d[1]; d[1] := d[i]; d[i] := x;

    j := 1; k := 2;

    while k < i do

    begin

      if (k + 1 < i) and (d[k + 1] > d[k]) then

        m := k + 1

      else

        m := k;

      if d[m] <= d[j] then break;

      x := d[j]; d[j] := d[m]; d[m] := x;

      j := m; k := j + j;

    end;

  end;

end;


begin

randomize;

for xx :=1 to N do

        d[xx] := random(1000);

        writeln('asdadsa');

HeapSort;

for xx :=1 to N do

        writeln(d[xx]);

readln;

end.

Używam FreePascal IDE (z dnia 10/04/2009).

Z góry dziękuję za odpowiedź!

Pozdrawiam!


(Marcin 110) #2

Algorytmy wydają się poprawne, heap sort jest paskudnie napisany i budujesz kopiec od złej strony - polecam jasną implementację z http://wazniak.mimuw.edu.pl/index.php?title=Algorytmy_i_struktury_danych/Sortowanie:_MergeSort%2C_HeapSort_i_QuickSort#Sortowanie_kopcowe_.28HeapSort.29 Wszystko jest zrzucone na jedną procedurę: popraw_kopiec.

Obydwa algorytmy wysypują się dla dużych danych. Jeśli zamienisz deklaracje integer na longint powinno być dobrze.


(Ziem) #3

Dzięki za odpowiedź!

Za chwilę to wypróbuję.

Wczoraj, jeśli dobrze pamiętam pisałeś o funkcji clock, co muszę dołączyć do programu, aby z niej skorzystać?

Pozdrawiam!


(Marcin 110) #4

Chodziło o analogię do clock z time.h dla C, ale to było w specyfikacji Sun'a, a FP chyba tego nie implementuje - więc usunąłem posta. może spróbuj GetTickCount() z modułu Windows lub fpTimes z modułu BaseUnix. http://www.freepascal.org/docs-html/rtl/baseunix/fptimes.html


(Ziem) #5

Dzięki wielkie za pomoc. Nareszcie zaczęło wszystko działać! :smiley: