5 Dos unit, rendezési algoritmusok
   

• dos unit

• rendezési algoritmusok

        
     5.1 Dos unit

     A dos unit segítségével többek között lekérhetjük az aktuális dátumot és idõt.

     A dátumot a getdate eljárás segítségével kérhetjük le. A parancsnak négy paramétere van. Ebbe a négy paraméterként megadott változóba adja vissza az eljárás az aktuális évet, hónapot, napot és azt, hogy a hét melyik napja van éppen (0-vasárnap, 1-hétfõ, ...).

     Hasonlóan működik az idõ lekérésére is a gettime eljárás. Paraméterként itt is négy változót kell megadnunk, melyekben visszakapjuk az aktuális órát, percet, másodpercet és századmásodpercet. Ennek az eljárásnak a segítségével fogjuk késõbb lemérni az egyes rendezési algoritmusok futásának idõtartamát.

program Pelda21;
uses dos;
var d1,d2,d3,d4,t1,t2,t3,t4:word;
begin
 getdate(d1,d2,d3,d4);
 gettime(t1,t2,t3,t4);
 write('Mai datum: ',d1,'. ',d2,'. ',d3,'. ');
 case d4 of
  0: writeln('vasarnap');
  1: writeln('hetfo');
  2: writeln('kedd');
  3: writeln('szerda');
  4: writeln('csutortok');
  5: writeln('pentek');
  6: writeln('szombat')
 end;
 writeln('Ido: ',t1,':',t2,':',t3,'.',t4);
end.

     A dos unit összes eljárásának, függvényének és konstansának részletes leírása mintapéldákkal megtalálható a FreePascal súgójában (dokumentációjában).

  
     5.2 Rendezési algoritmusok

     Adott egy tömb, melyben véletlenszerű számok vannak. Feladatunk, hogy rendezzük ezeket a számokat növekvõ sorrendbe különbözõ algoritmusok segítségével. A rendezés idejét minden esetben mérjük le századmásodpercekben.

     Egyszerű rendezés (SimpleSort)

     Ez a programilag legegyszerűbb rendezési algoritmus. Mindegyik elemet összehasonlítjuk az összes utána következő elemmel két egymásba ágyazott ciklus segítségével. Ha az éppen összehasonlított két elem nem jó sorrendben van, akkor azokat rögtön ki is cseréljük.

     Rendezés a legkisebb elem kiválasztásával (MinSort, SelectSort)

     A módszer lényege, hogy az i. helyre ( i = 1,2,3,... ) sorban kiválasztjuk az i...elemekszama helyen levõk közül a legkisebbet.

     Rendezés a szomszédos elemek cseréjével (BubbleSort)

     A módszer lényege, hogy egyesével végignézzük a szomszédos elemeket, és ha elõbb van a nagyobb, megcseréljük azokat. Így biztosan a legnagyobb helyre kerül a legnagyobb elem ("a buborék felszáll"). Ugyanezt sorban végrehajtjuk az utolsó elõtti elemig stb., egészen az elsõig. Ha közben kiderül, hogy a tömb rendezett, az eljárást befejezzük.

     Rendezés beszúrásos módszerrel (InsertSort)

     A módszer hasonlít a kártyák kézben való rendezéséhez. Mindig vesszük a következõ elemet, s azt a megfelelõ helyre beszúrjuk úgy, hogy a többi, már rendezett elemet eggyel feljebb toljuk.

     Mindhárom rendezés pontos algoritmusa megtalálható az alábbi programban:

program Pelda22;
uses crt, dos;
const elemekszama = 30000;
var a,b:array [1..elemekszama] of integer;
    ido:longint;
     i:integer;

procedure kiiras;
var i:integer;
begin
 for i:=1 to elemekszama do write(a[i],' ');
 writeln;
 writeln;
end;

procedure stopperbe;
var t1,t2,t3,t4:word;
begin
 gettime(t1,t2,t3,t4);
 ido:=t4+100*(t3+60*(t2+60*t1));
end;

procedure stopperki;
var t1,t2,t3,t4:word;
begin
 gettime(t1,t2,t3,t4);
 ido:=t4+100*(t3+60*(t2+60*t1))-ido;
end;

{ egyszeru rendezes }
procedure simplesort;
var i,j,x:integer;
begin
 for i:=1 to elemekszama-1 do
  for j:=i+1 to elemekszama do
     if a[i]>a[j] then begin
                        x:=a[i];
                        a[i]:=a[j];
                        a[j]:=x;
                       end;
end;

{ rendezes a legkisebb elem kivalasztasaval }
procedure minsort;
var i,j,min,x:integer;
begin
 for i:=1 to elemekszama-1 do
  begin
   min:=i;
   for j:=i+1 to elemekszama do
     if a[j]<a[min] then min:=j;
   x:=a[i];
   a[i]:=a[min];
   a[min]:=x;
  end;
end;

{ rendezes a szomszedos elemek cserejevel }
procedure bubblesort;
var i,j,x:integer;
    ok:boolean;
begin
 i:=elemekszama-1;
 ok:=false;
 while (i>=1) and (not ok) do
  begin
   ok:=true;
   for j:=1 to i do
     if a[j]>a[j+1] then begin
                         x:=a[j];
                         a[j]:=a[j+1];
                         a[j+1]:=x;
                         ok:=false;
                         end;
   dec(i);
  end;
end;

{ rendezes beszurasos modszerrel }
procedure insertsort;
var i,j,x,ment:integer;
begin
 for i:=2 to elemekszama do
  begin
   if a[i]<a[i-1] then begin
                       ment:=a[i];
                       j:=i;
                       repeat
                        dec(j);
                        a[j+1]:=a[j];
                       until (j=1) or (a[j-1]<=ment);
                       a[j]:=ment;
                       end;
  end;
end;

{ foprogram }
begin
 clrscr;
 writeln(elemekszama,' drb. elem rendezese:');
 writeln;
 randomize;
 for i:=1 to elemekszama do b[i]:=random(64000)-32000;
 { mindig a-t fogjuk rendezni, b-ben meghagyjuk a kigeneralt szamokat}
 a:=b;
 { rendezes }
 stopperbe;
 simplesort;
 stopperki;
 { kiiras }
 writeln('SimpleSort: ',ido,' szazadmasodperc');
 a:=b;
 { rendezes }
 stopperbe;
 minsort;
 stopperki;
 { kiiras }
 writeln('MinSort: ',ido,' szazadmasodperc');
 a:=b;
 { rendezes }
 stopperbe;
 bubblesort;
 stopperki;
 { kiiras }
 writeln('BubbleSort: ',ido,' szazadmasodperc');
 a:=b;
 { rendezes }
 stopperbe;
 insertsort;
 stopperki;
 { kiiras }
 writeln('InsertSort: ',ido,' szazadmasodperc');
end. 
    

    A rendezési algoritmusokat animációk segítségével bemutató program letölthető itt:
   

rendalgo.exe