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:
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.
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...
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.
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é.
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.
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.
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.)
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 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.