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