Rendezések algoritmusa

Rendezések

A rendezés a legalapvetőbb programozási probléma. Van néhány adatunk és ezeket valamilyen szempont szerint nagyság szerinti sorrendbe kell rendeznünk.

Buborék
Az algoritmus alkalmazásának feltétele hogy a sorozat elemeihez létezzen egy rendezési reláció.

Az algoritmus újra és újra végigiterál a listán, összehasonlítja a lista szomszédos elemeit, és ha azok az elvárt rendezéshez képest fordítva vannak, akkor megcseréli őket. Első menetben a lista elejéről indul és a végéig megy. Ennek az első menetnek az eredményeként a legnagyobb elem (mint egy buborék) felszáll a lista végére. Így a következő menetben már elegendő az utolsó előtti elemig elvégezni a szomszédos elemek összehasonlítását és cseréjét. Az ezután következő menetben a lista utolsó két eleme lesz a helyén és így tovább...

Az algoritmus két egymásba ágyazott ciklusból áll. A tömb első elemének indexe az 1, elemeinek száma pedig n. Az elemek itt számok, és a reláció a > (nagyobb).

   CIKLUS i = n TŐL i > 0 IG {
       CIKLUS j = 0 TÓL i-1 IG {
           HA TOMB[j] > TOMB[j+1] AKKOR {
               CSERÉLD FEL ŐKET: TOMB[j], TOMB[j+1]
           }
       }
   }
A futás befejezése után a tömb 1-es indexű eleme lesz a legkisebb és az n indexű a legnagyobb.


A buborékrendezés illusztrálása. Az (x, y) pont jelentése: az y érték a tömb x-edik eleme.
Az algoritmus onnan kapta a nevét, hogy először a legnagyobb elem „száll fel” a tömb utolsó helyére, utána a második legnagyobb az azt követő helyre, és így tovább, mint ahogy a buborékok szállnak felfelé egy pohárban.

Ebben a pontban csak olyan rendezésekkel foglalkozunk  ahol a rendezendő adatok elférnek a központi memóriában. Feltesszük tehát, hogy az adatok egy a[ ] tömbben vannak. Az algoritmusokat lehetőség szerint függetleníteni szeretnénk a programozási nyelvektől, ezért bevezetünk két jelölést: a tömb első elemének indexe E, utolsó elemének indexe pedig U lesz.

A rendezést általában összetett objektumokon hajtjuk végre, ilyenkor a sorrendet valamelyik mező adja meg, amit szokás rendezési kulcsnak hívni. Az algoritmusainkban elrejtjük ezt a részletet és úgy fogalmazzuk meg a módszereket, hogy mindenhol az a[i] < a[j] összehasonlítást használjuk. Egy külön pontban vizsgáljuk azt, hogy hogyan lehet típus- és objektumfüggetlen rendezést írni.

Algoritmus
Ciklus i := E-től (U-1)-ig
    min := i
    Ciklus j := (i+1)-től U-ig
        Ha a[j] < a[min] akkor min := j Elágazás vége
    Ciklus vége
    Csere(i, min)
Ciklus vége

A rendezés után az első helyre a legkisebb elem kerül. Tehát ha megtaláljuk a minimális elemet, becserélhetjük az első helyre. Ezután a második elemtől kezdődő résztömbben kell megkeresnünk a minimális elemet, és azt érdemes a második helyre cserélni....

A rendezés tehát futamokból fog állni. Egy futamban az i. indexű elemtől az utolsó elemig tartó rész minimumát keressük meg, és ezt az i. pozícióra cseréljük.


A tömbre úgy gondolunk, mintha két részből állna: az első i elem már rendezett résztömböt alkot, a többi elemet pedig még nem vizsgáltuk. Most következik az (i+1)-dik elem. Őt szeretnénk beilleszteni az első i közé úgy, hogy most már az első i+1 elemből álló résztömb is rendezett legyen. Ez ahhoz hasonló, mint amikor a kártyás kézben sorba teszi lapjait: balról indul és a következő lapot mindig beszúrja a helyére az addig rendezett lapok közé.

A beszúrás úgy történik, hogy amíg a vizsgált elem kisebb, mint a tőle balra álló, addig felcseréljük vele. Figyelni kell arra is, hogy nem értünk-e ki a tömb bal szélére, mert ott leáll a cserélgetés.

Algoritmus
Ciklus i:= (E+1)-től U-ig
    j := i - 1
    Ciklus amíg j >= E és a[j] > a[j+1]
        Csere(j, j+1)
         j := j - 1
    Ciklus vége
Ciklus vége

Összefésülés
A tömböt két részre vágjuk (lehetőleg fele-fele arányban), a részeket külön-külön rendezzük (rekurzió!), majd a rendezett részeket összefésüljük.
Összefésülés
A rendezett tömbök első elemire állunk, és minden lépésben a két aktuális elem közül a kisebbet tesszük az eredmény tömbbe, majd annak mutatóját növeljük. Ha valamelyik részt végigolvastuk már, akkor egyszerűen a másik részből másolgatjuk az elemeket.

Algoritmus
rendez(E, U):

    Ha E < U akkor
        K := (E+U) / 2
        rendez(E,K)
        rendez(K+1,U)
        összefésül(E,K,U)
    Elágazás vége


összefésül(E,K,U):

    tmp[E..U] : = a[E..U] // tömb másolása átmeneti tárolóhelyre
    i := E; j := K+1
    Ciklus id := E-től U-ig
        Ha i > K akkor
            a[id] := tmp[j]
            j := j+1
        különben Ha j > U akkor
            a[id] := tmp[i]
            i := i+1
        különben Ha tmp[i] < tmp[j] akkor
            a[id] := tmp[i]
            i := i+1
        különben
            a[id] := tmp[j]
            j := j+1
        Elágazás vége
    Ciklus vége

Gyorsrendezés
A gyorsrendezés az összefésülő rendezés egy lehetséges továbbfejlesztett változata. Előnye az összefésülő rendezéshez képest az, hogy nem szükséges egy második tömb az összefésülésekhez, vagyis feleakkora a memóriaigénye. Általában rekurzív módon szokás megfogalmazni.
Gondolat
A tömböt az első eleme szerint (helyben) szétválogatjuk. Ha az első elem értéke X, akkor a tömb elejére kerülnek az X-nél nem nagyobb, a végére pedig az X-nél nem kisebb elemek, és "középre" X. Ezután az X-nél kisebb és az X-nél nagyobb elemeket rekurzív rendezzük. Ez a megközelítés akkor rendez gyorsan, ha a szétválogatások "nagyjából" egyenlő részekre vágják az aktuális tömböket. A "rossz" bemeneteket úgy szokás kiküszöbölni, hogy a gyorsrendezés előtt összekeverjük a tömböt (ez lineáris algoritmussal megtehető.)

Algoritmus
Gyorsrendezés
gyorsrendez(a, E, U):
    kever(a, E, U)
    rendez(a, E, U)
eljárás vége


rendez(a, E, U):
    Ha E < U akkor
        K = szétválogat(a, E, U)
        rendez(a, E, K-1)
        rendez(a, K+1, U)
    Elágazás vége
eljárás vége

Kupacrendezés
A kupac adatszerkezet használatával O(N log N)-es rendezés készíthető.

kupacrendez(T,N):

    //kezdeti kupac felépítése

    Ciklus i := N/2-től 1-ig
        süllyeszt(i)
    Ciklus vége


    //maximális elemek helyretétele egymás után

    Ciklus i:=1-től (N-1)-ig
        csere(T,1,N-i+1)
        süllyeszt(1)
    Ciklus vége

eljárás vége

Kupac
A kupac adatszerkezet - többek között - rendezésre, illetve prioritási sorok megvalósítására használható. Ereje, hogy időben dinamikusan változó adatszerkezetben hatékonyan tudja megadni az aktuális legnagyobb (vagy legkisebb) elemet.
A kupac definíciója
A kupac egy olyan bináris fa, amely
majdnem teljesen kiegyensúlyozott, vagyis a legalsó szint kivételével minden csomópontnak van bal és jobb gyermeke, vagy nincs se bal se jobb gyermeke;
bármely csomópontban lévő elem kulcsa nagyobb (kisebb) a csomópont gyermekeiben tárolt elemek kulcsánál.
A  fentiekből következik, hogy a kupac tetején (a bináris fa gyökerében) lévő elem maximális (minimális), és ez a tulajdonság rekurzívan igaz bármely rész-kupacra (a fa egy csomópontjából induló részfára).

A következő ábrán egy maximum-kupac látható, tehát egy olyan kupac, amelyben bármely elem kulcsa nagyobb vagy egyenlő, mint gyermekeinek kulcsa.