Rendezési algoritmusok
A feladat
Egy N elemű T[] tömb elemeit kell nagyság szerint növekvő sorrendbe rakni.
Az elmélet
Két elem összehasonlításakor három választ kaphatunk (<, =, >), tehát $k$ kérdéssel legfeljebb
$3^k$ lehetőség között tudunk választani. Az $\,N$ elemnek $\,N!$-féle sorrendje van,
ezek közül kell az egyetlen jót meghatároznunk, tehát szükségszerűen $N! \le 3^k$. Kettes alapú logaritmust véve innen $\log N! /\log 3 \le k$. Finomabb matematikai eszközökkel megmutatható, hogy
$\log N! \approx c\cdot N\log N$, ennél gyorsabb rendező algoritmus nem készíthető. (Ez természetesen csak azokra a rendezésekre vonatkozik, amelyek a tömbelemek összehasonlításával és cserélgetésével működnek.)
A legegyszerűbb rendező algoritmusok általában $N^2$-tel arányos lépésszámmal dolgoznak, a kupacrendezés és a gyorsrendezés elméletileg optimális. Óvatosan kell azonban bánnunk az elméleti becslésekkel, a nagyságrend szempontjából elhanyagolt konstansokon néha sok múlik. "Kis" tömbök esetén az egyszerű cserés rendezések is tökéletesen megfelelnek. Gondolatébresztőnek egy kis táblázat. (Az egyszerűség kedvéért 10-es alapú logaritmussal számolva.)
| $\,N$ | $N^2$ | $1000N\log N$ |
| 10 | 100 | 10000 |
| 100 | 10000 | 200000 |
| 1000 | 1000000 | 3000000 |
| 10000 | 100000000 | 40000000 |
A bemutatott példák közül a Shell rendezés látszik a leggyorsabbnak, de ez csak
$N = 100$ miatt van így.
Nagy adathalmazok esetén a kupacrendezés és a gyorsrendezés is hatékonyabb.
Algoritmusok
Az algoritmusok többségében használjuk a csere(i,j) eljárást, ami az alábbi műveleteket végzi:
tmp := T[i]; T[i] := T[j]; T[j] := tmp
Egyszerű cserés rendezés
Az aktuális első elemet összehasonlítjuk a második, harmadik, ... elemmel. Ha az aktuális első elem nagyobb, cserélünk.
A külső ciklus első lefutásakor helyére kerül a legkisebb elem. Ezután a külső ciklus továbblép, és a helyretett elem kikerül a rendezendő szakaszból. A külső ciklus $i.$ lefutásan után az első $i$ elem rendezett.
A belső ciklus lefutásakor egyre kisebb értékű elemekkel cseréljük az éppen vizsgált tagot, emiatt alakul ki az a jellegzetes kép, hogy a rendezett szakasz után nagyjából fordítottan rendezett szakasz jelenik meg.
Ciklus i := 1-től (N-1)-ig
Ciklus j := (i+1)-től N-ig
Ha T[i] > T[j] akkor
Csere(i,j)
Elágazás vége
Ciklus vége
Ciklus vége
Minimumkiválasztásos rendezés
Megkeressük a legkisebb elemet és betesszük az első helyre. Ezután az első elemmel tovább nem foglalkozunk,
a megmaradt $N-1$ elemmel megismételjük az eljárást. Most már az első két elem került helyre, stb...
Ciklus i := 1-től (N-1)-ig
min := i
Ciklus j := (i+1)-től N-ig
Ha T[j] < T[min] akkor min := j Elágazás vége
Ciklus vége
Ha min <> i akkor Csere(i,min) Elágazás vége
Ciklus vége
Buborék rendezés
Menetenként végignézzük a szomszédos elemeket a tömb elejétől a vége felé haladva, és felcseréljük a rosszul rendezett párok tagjait. Egy menetben a legnagyobb elem a tömb végére kerül. Ezután eggyel rövidebb tömbbel folytatjuk az eljárást...
Ha egy menetben nem történt csere, a teljes tömb rendezett és megállhatunk.
Ciklus i := (N-1)-től 1-ig
voltCsere := HAMIS
Ciklus j := 1-től i-ig
Ha T[j] > T[j+1] akkor
Csere(j,j+1)
voltCsere := IGAZ
Elágazás vége
Ciklus vége
Ha nem voltCsere akkor kilépés Elágazás vége
Ciklus vége
Kétirányú buborék rendezés
A buborék rendezés javítása. Egy menetben a legkisebb és legnagyobb elemet tesszük helyre, így
egyszerre mozognak a kis elemek a tömb eleje, a nagyok pedig a tömb vége felé.
vége := N+1; eleje := 0
Ciklus amíg eleje < vége
eleje := eleje + 1; vége := vége - 1; voltCsere := hamis
Ciklus j := eleje-től (vége-1)-ig
Ha T[j] > T[j + 1] akkor
Csere(j,j + 1)
voltCsere := igaz
Elágazás vége
Ciklus vége
Ha nem voltCsere akkor
Kilépés
különben
voltCsere := hamis
Elágazás vége
Ciklus j := (vége-1)-től eleje-ig (-1)-esével
Ha T[j] > T[j + 1] akkor
Csere(j,j + 1)
voltCsere := igaz
Elágazás vége
Ciklus vége
Ha nem voltCsere akkor Kilépés Elágazás vége
Ciklus vége
Shell rendezés
Az algoritmus alapötlete az, hogy ne csak a szomszédos elemeket hasonlítsuk össze, hanem először távoli indexű értékeket
nézzünk, majd folyamatosan csökkentsük a távolságot. Sokan vizsgálták azt a kérdést, hogy milyen távolságsorozat adja a
legjobb futási időt.
A most bemutatott változatban a D.E. Knuth által javasolt
h[] = {1,4,13,40,121} távolságsorozattal dolgozunk.
Tetszőleges távolságsorozat helyes rendezést biztosít, ha a legkisebb lépés értéke 1.
Ciklus s := 5-től 1-ig (-1)-esével
lep := h[s]
Ciklus j := (lep+1)-től N-ig
i := j - lep; x := T[j]
Ciklus amíg i > 0 és T[i] > x
T[i+lep] := T[i]
i = i - lep
Ciklus vége
T[i+lep] := x
Ciklus vége
Ciklus vége
Kupac rendezés
A tömböt kupaccá alakítjuk. A kupac tetejére kerül a legnagyobb elem, ezt a tömb végén lévő elemmel felcseréljük, csökkentjük a kupac méretét és helyreállítjuk a kupac-tulajdonságot. A buborékrendezéshez hasonlóan itt is minden menetben
az aktuális szakasz legnagyobb eleme kerül helyére. Egy menet azonban sokkal gyorsabb, mert a kupac-tulajdonság helyreállítása
$\log N$-nel arányos lépésben megy, míg a buborék rendezésnél egy-egy menet $N$-nel arányos lépést végez. (Részletesebb magyarázat a kupac adatszerkezet leírásánál.)
bal(k):
bal := 2 * k
Eljárás vége
jobb(k):
jobb := 2 * k + 1
Eljárás vége
epit(T):
Ciklus i := (N/2)-től 1-ig (-1)-esével
sullyeszt(N,i,T)
Ciklus vége
Eljárás vége
sullyeszt(p, r, T):
b := bal(r); j := jobb(r)
Ha b<=p és T[b]>T[r] akkor max := b különben max := r Elágazás vége
Ha j<=p és T[j]>T[max] akkor max := j Elágazás vége
Ha max != r akkor
Csere(max,r)
sullyeszt(p,max,a);
Elágazás vége
Eljárás vége
rendez(T):
db := N
epit(T)
Ciklus i := db-től 1-ig (-1)-esével
Csere(1,i)
db --;
sullyeszt(db,1,T);
Ciklus vége
Eljárás vége
Gyorsrendezés
A középső indexű elem szerint kettéválogatjuk a tömböt.
Alulra kerülnek a középsőnél kisebbek, felülre pedig a nagyobbak. Ezután az alsó és a felső részre
rekurzívan meghívjuk a rendező eljárást.
A rendezést a QuickSort(T, 1, N) hívással indíthatjuk el.
A rekurzív módszer akkor hatékony, ha elég sokszor nagyjából két egyenlő részre bontjuk az éppen rendezendő szakaszt.
Mivel az eredeti adatsorról nem feltételezhetünk semmit, nem biztos, hogy a középső indexű elem adja a legjobb kettéosztást.
A gyorsrendezés egyik gyakran használt változatában véletlenszerűen választjuk ki a kettéosztást definiáló "pivot elemet", ezzel kivédjük a "rossz" adatsorból adódó lassulást.
QuickSort(T, lo0, hi0):
lo = lo0;hi = hi0;
Ha hi0 > lo0 akkor
mid = T[ ( lo0 + hi0 ) / 2 ]
Ciklus amíg lo <= hi
Ciklus amíg ( lo < hi0 ) és ( T[lo] < mid ) lo := lo + 1 Ciklus vége
Ciklus amíg ( hi > lo0 ) és ( T[hi] > mid ) hi := hi - 1 Ciklus vége
Ha lo <= hi akkor
Csere(lo, hi)
lo := lo + 1
hi := hi - 1
Elágazás vége
Ciklus vége
Ha lo0 < hi akkor QuickSort( T, lo0, hi ) Elágazás vége
Ha lo < hi0 akkor QuickSort( T, lo, hi0 ) Elágazás vége
Elágazás vége
