Pascal I.      Pascal II.      Delphi       Linkek     
Pascal II.
01. Eljárások, függv...
01. Gyakorló feladatok
02. Felsorolt típus, ...
02. Gyakorló feladatok
03. Állományok kezelése
03. Gyakorló feladatok
04. Unitok, CRT unit
04. Gyakorló feladatok
05. DOS unit, rendezé...
05. Gyakorló feladatok
06. Rekurzió, quicksort
06. Gyakorló feladatok
07. Backtracking
07. Gyakorló feladatok
08. GRAPH unit
08. Gyakorló feladatok
09. Kép mozgatása
09. Gyakorló feladatok
10. Winmouse unit
10. Gyakorló feladatok
11. Dinamikus adatsze...
11. Gyakorló feladatok
12. Dinamikus adatsze...
12. Gyakorló feladatok
13. Dinamikus adatsze...
13. Gyakorló feladatok
Programozás 2 (Pascal)


     6 Rekurzió, quicksort
   

  • rekurzió

  • quicksort

        
     6.1 Rekurzió

     Rekurzió az, amikor egy eljárás vagy függvény - közvetve vagy közvetlenül - önmagát hívja. A végtelen rekurzió elkerülésére mindig szükségünk van egy feltételre, amely valamilyen lépésszám után leállítja a rekurziót. A következõ program eljárása ciklus helyett rekurziót alkalmaz adott számú csillag kirajzolására:

program Pelda23;
uses crt;

procedure csillagok(mennyi:integer);
begin
 if mennyi>0 then begin
                  write('*');
                  csillagok(mennyi-1);
                  end;
end;

begin
 clrscr;
 csillagok(10);
end.

     Az elv: adott számú csillagot úgy rajzolunk ki, hogy kirajzolunk egy csillagot, majd kirajzoljuk a maradékot. A mennyi paraméter azt jelzi, hogy mennyi csillagot kell még kirajzolni.

     A matematikában találkozhatunk rekurzív definíciókkal, pl. 0! (nulla faktoriális) értéke 1, n! pedig n*(n-1)!. Tehát egy szám faktoriálisát úgy számíthatjuk ki, hogy kiszámítjuk a nála eggyel kisebb szám faktoriálisát és megszorozzuk a számmal. A rekurzió véget ér, ha eljutunk a 0-hoz. Ez pascal programban így néz ki:

program Pelda24;
uses crt;
var k:integer;

function fakt(n:integer):longint;
begin
 if n>0 then fakt:=n*fakt(n-1)
        else fakt:=1;
end;

begin
 clrscr;
 write('Kerek egy egesz szamot (0..12): ');
 readln(k);
 writeln(k,'! = ',fakt(k));
end.

  
     6.2 Gyorsrendezés (QuickSort)

     A módszer lényege: Tekintsük a tömb középsõ elemét (felezzük a tömböt). Ez az elem az ú.n. pivot (vezérelem). Balról keressük meg azt az elsõ elemet, mely ennél nem kisebb, jobbról azt az elsõ elemet, amely ennél nem nagyobb. Cseréljük ki a két elemet, s folytassuk a cserélgetést egészen addig, amíg a bal oldalon a középsõ elemnél (mely természetesen cserélõdhet menet közben) csupa nem nagyobb, jobb oldalon pedig csupa nem kisebb elem áll. Rekurzív hívással most rendezzük a tömb alsó és felsõ felét, majd ezeknek alsó és felsõ felét, és így tovább.

     A QuickSort-tal kiegészített rendezést bemutató program:

program Pelda25;
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;

{ gyorsrendezes }
procedure quicksort(bal,jobb:integer);
var i,j,pivot,x:integer;
begin
 i:=bal;
 j:=jobb;
 pivot:=a[(i+j) div 2];
 while i<=j do
  begin
   while a[i]<pivot do inc(i);
   while a[j]>pivot do dec(j);
   if i<=j then begin
                x:=a[i];
                a[i]:=a[j];
                a[j]:=x;
                inc(i);
                dec(j);
                end;
  end;
 if bal<j then quicksort(bal,j);
 if i<jobb then quicksort(i,jobb);
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');
 a:=b;
 
{ rendezes }
 stopperbe;
 quicksort(1,elemekszama);
 stopperki;
 
{ kiiras }
 writeln('QuickSort: ',ido,' szazadmasodperc');
end. 
    

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


rendalgo.exe

    

(C) 2004-2013, PaedDr. Végh Ladislav, Komárno, Szlovákia