Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

4.2. Rendezés

4.2. Rendezés

4.7. Definíció. A reláció

Valamely halmaz esetén a részhalmazt az halmazon értelmezett relációnak nevezzük. Azt mondjuk, hogy az halmaz és eleme a relációban van, ha . Röviden ezt így írjuk: .

4.3. Példa. Legyen , és a reláció a kisebb ,, ” jel. Az reláció azokat a számpárokat jelenti, amelyekre fennáll az összefüggés.

4.8. Definíció. A rendezési reláció

A relációt rendezési relációnak nevezzük az halmazon, ha

Például a valós számok közötti ,, ” reláció rendezési reláció.

Rendezésről olyan adattípus esetén beszélhetünk, amelyre értelmezve van egy rendezési reláció. Tekintsük a sorozatot és annak is vegyük a tömbös realizációját. A rendezés a sorozat elemeinek olyan felsorolását jelenti, amelyben az egymást követő elemek a megadott relációban vannak. A tárgyalást valós számokon (leginkább egészek) visszük végig és relációnak a kisebb, egyenlő relációt () tekintjük. ami nem csökkenti az általánosságot. A rendezés mind a mai időkig fontos informatikai probléma. Gyakran jelenik meg mint egy nagyobb probléma része. A rendezési algoritmusokkal kapcsolatban több szempont szerinti igény léphet föl. Ilyenek például az alábbiak:

Nem lehet kizárni a nem optimális algoritmusokat sem az alkalmazásokból, mert egy probléma megoldásában nem csak a rendezési algoritmus optimalitása az egyetlen szempont a problémamegoldás hatékonyságára. (Hiába gyors az algoritmus, ha az adatok nem a kívánt formában állnak rendelkezésre, és a konverzió lerontja a hatékonyságot.)

4.2.1. A beszúró rendezés

A beszúró rendezés alapelve nagyon egyszerű. A sorozat második elemétől kezdve (az első önmagában már rendezett) egyenként a kulcsokat a sorozat eleje felé haladva a megfelelő helyre mozgatjuk összehasonlítások révén. A sorozatnak a vizsgált kulcsot megelőző elemei mindig rendezettek az algoritmus során.

4.4. Példa. Az alábbi kulcsok esetén nyíl mutatja a mozgatandó kulcsot és a beszúrás helyét.

Egy másik példa animációként:

Feladat: Számítsuk ki, hogy a beszúró rendezésre a !

Feladat: Készítsük el a beszúró rendezésre a pszeudokódot, ha a kulcsok egy kétszeresen láncolt listával vannak megadva!

4.2.2. Az összefésülő rendezés

Az összefésülő rendezés alapelve az összefésülés műveletén alapszik, amely két rendezett tömbből egy új rendezett tömböt állít elő. Az összefésülés folyamata: Mindkét tömbnek megvizsgáljuk az első elemét. A két elem közül a kisebbiket beírjuk az eredménytömb első szabad eleme helyére. A felszabaduló helyre újabb elemet veszünk abból a tömbből, ahonnan előzőleg a kisebbik elem jött. Ezt a tevékenységet folytatjuk mindaddig, míg valamelyik kiinduló tömbünk ki nem ürül. Ezután a még vizsgálat alatt lévő elemet, valamint a megmaradt másik tömb további elemeit sorba az eredménytömbhöz hozzáírjuk a végén. Az eredménytömb nem lehet azonos egyik bemeneti tömbbel sem, vagyis az eljárás nem helyben végzi az összefésülést.

Legyen ÖSSZEFÉSÜL (A, p, q, r) az az eljárás, amely összefésüli az és az résztömböket, majd az eredményt az eredeti helyre másolja vissza. Az eljárás lineáris méretű további segédmemóriát igényel. Az összefésülés időigénye , ha összesen elemünk van. (Egy menetben elvégezhető és az kell is hozzá.)

4.9. Definíció. Az oszd meg és uralkodj elv

Az oszd meg és uralkodj elv egy algoritmus tervezési stratégia A problémát olyan kisebb méretű, azonos részproblémákra osztjuk föl, amelyek rekurzívan megoldhatók. Ezután egyesítjük a megoldásokat.

Az összefésülő rendezés oszd meg és uralkodj típusú algoritmus, melynek az egyes fázisai:

A teljes tömb rendezését megoldó utasítás: ÖSSZEFÉSÜLŐ_RENDEZÉS(A,1,hossz[A]).

Az összefésülő rendezés időigénye

Az algoritmus időigénye megkapható a mester tétel 2. pontja alapján: .

4.2.3. A Batcher-féle páros-páratlan összefésülés

Az eljárás csak az összefésülést teszi hatékonyabbá. Nem önálló rendező módszer. Nagy előnye, hogy párhuzamosíthatók a lépései. Legyen két rendezett sorozatunk, az n elemű A sorozat és az m elemű B sorozat.

A két sorozat összefésülése adja a sorozatot. Az összefésülés módja a következő: Mindkét kiinduló sorozatból kettőt képezünk, a páratlan indexű és a páros indexű elemek sorozatait:

Összefésüljük az sorozatokat, eredménye az sorozat.

Összefésüljük az sorozatokat, eredménye a sorozat.

Összefésüljük az és sorozatokat, eredmény a sorozat.

4.10. Tétel. A Batcher-féle összefésülés tétele

A Batcher összefésülés során

és

ahol .

Bizonyítás. Fogadjuk el kiindulásként igaznak azt a feltevést, hogy elejéből páros számú elemet véve azok között azonos számú és elem van. Ekkor

és

Ebből viszont

ahonnan miatt adódik a tétel állítása.

A feltételezésünk bizonyítása:

Legyen

Ezek közül -ba kerül elem az -ból (az páratlan indexű elemei) és elem a -ből (a páros indexű elemei), valamint -be kerül elem az -ból (az páros indexű elemei) és elem a -ből (a páratlan indexű elemei). Innen az -beliek száma

és a -beliek száma

4.2.4. Gyorsrendezés (oszd meg és uralkodj típusú algoritmus)

A gyorsrendezés időigénye:

A legrosszabb eset: a felosztás minden lépésben elemű

Innen

A legjobb eset: a felosztás, ekkor

Ez megegyezik az összefésülő módszer formulájával, tehát

Megjegyzés: ha a felosztás aránya állandó pl. akkor a rekurziós formula:

Bizonyíthatö, hogy ekkor is

Ezen túlmenően az átlagos értékre is adódik.

4.2.5. A buborékrendezés

A buborékrendezésnél az egymás mellett álló elemeket hasonlítjuk össze, és szükség esetén sorrendjüket felcseréljük. Ezt mindaddig folytatjuk, míg szükség van cserére.

Időigény a legrosszabb esetben: .

Az algoritmusra jellező a sok csere, az elem lassan kerül a helyére.

4.2.6. A Shell rendezés (rendezés fogyó növekménnyel)

A Shell rendezés a buborékrendezésnél tapasztalt lassú helyrekerülést igyekszik felgyorsítani azáltal, hogy egymástól távol álló elemeket hasonlít és cserél fel. A távolságot (itt növekménynek nevezik) fokozatosan csökkenti, míg az 1 nem lesz. Minden növekmény esetén beszúrásos rendezést végez az adott növekménynek megfelelő távolságra álló elemekre. Mire a növekmény 1 lesz, sok elem már majdnem a helyére kerül.

A növekmények felépítése. Használjunk számú növekményt. Legyenek ezek .

A követelmény: , és .

A szakirodalomban javasolt növekményadatok:

Megjegyzés: A hossz[A] a rendezendő elemek számát jelöli.

Időigény: alkalmas növekmény választással leszorítható -re.

4.2.7. A minimum kiválasztásos rendezés

Ebben a rendezésben -szer végigmegyünk a tömbön. Minden alkalommal eggyel magasabb indexű elemtől indulunk. Megkeressük a minimális elemet, és azt az aktuális menet kezdő elemével felcseréljük.

Időigény: összehasonlításszám .

4.2.8. Négyzetes rendezés

Felosztjuk az elemű tömböt (közel) számú részre (alcsoportra). Mindegyikben (közel) elemet helyezünk el, majd mindegyikből kiemeljük (eltávolítjuk) a legkisebbet. A kiemeltekből egy főcsoportot képzünk. Kiválasztjuk a főcsoport legkisebb elemét és azt az eredménytömbbe írjuk, a főcsoportból pedig eltávolítjuk (töröljük). Helyére abból az alcsoportból ahonnan ő származott újabb legkisebbiket emelünk be a főcsoportba. Az eljárást folytatjuk, míg az elemek el nem fogynak a főcsoportból.

Időigény: összehasonlításszám .

Továbbfejlesztett változat, amikor számú elem van egy fő-főcsoportban és számú főcsoport van, mindegyikben számú elemmel, melyek mindegyikéhez egy elemszámú alcsoport tartozik. A rendezés elve az előző algoritmuséhoz hasonló.

Időigény:

4.2.9. A Stirling formula és az Alsó korlát összehasonlító rendezésre tétel

4.11. Tétel. A Stirling formula

Igaz az alábbi összefüggés az n!-ra:

Bizonyítás. Az egyenlőtlenséget a logaritmusra látjuk be. A logaritmus függvény konkáv és emiatt írható:

Az összehasonlító módszerek döntési fája

4.12. Tétel. Alsó korlát összehasonlító rendezésre

Bármely elemet rendező döntési fa magassága

Bizonyítás. Egy magasságú döntési fa leveleinek száma legfeljebb . Mivel minden permutációt rendezni kell tudnia az algoritmusnak, és összesen permutáció lehetséges, ezért a döntései fának legalább levele kell legyen.

Tehát fennáll. Logaritmálva: . A Stirling formula szerint . Behelyettesítve: .

Tehát:

4.2.10. Lineáris idejű rendezők: A leszámláló rendezés

A lineáris idejű rendezők nem használják az összehasonlítást.

A leszámláló rendezés ( = binsort, ládarendezés) bemenete 1 és k közötti egész szám.

Időigény: . Ha , akkor a rendezési idő is , ahol .

Az elemeket az tömbben helyezzük el. Szükség van további két tömbre: az eredményt tárolja majd, segédtömb.

A rendezés lényege, hogy A minden elemére meghatározza a nála kisebb elemek számát. Ez alapján tudja az elemet a kimeneti tömb megfelelő helyére tenni. Stabil eljárás: az azonos értékűek sorrendje megegyezik az eredetivel

4.2.11. A számjegyes rendezés (radix rendezés)

Azonos hosszúságú szavak, stringek rendezésére használhatjuk. (Dátumok, számjegyekből álló számok, kártyák, stb.) Legyen a szó hossza, pedig az egy karakteren, mezőben előforduló lehetséges jegyek, jelek száma, pedig az adatok száma.

Időigény:

4.2.12. Edényrendezés

Feltételezzük, hogy a bemenet a intervallumon egyenletes eloszlású számok sorozata. Felosztjuk a intervallumot egyenlő részre (edények). A bemenetet szétosztjuk az edények között, minden edényben egy listát kezelve. Az azonos edénybe esőket beszúrásos módon rendezzük. A végén a listákat egybefűzzük az elsővel kezdve.

Várható időigény:

4.2.13. Külső tárak rendezése

Külső tárak rendezésénél az elérési és a mozgatási idő szerepe drasztikusan megnő. Az összefésüléses módszerek jönnek elsősorban számításba.

4.13. Definíció. A k hosszúságú futam file-ban

Egy file szomszédos rekordjából álló részét k hosszúságú futamnak nevezzük, ha benne a rekordkulcsok rendezettek (pl.: növekedő sorrendűek).

Először alkalmas -val ( mindig megfelel) a rendezendő file-t két másik file-ba átmásoljuk úgy, hogy ott hosszúságú futamok jöjjenek létre. Ezután a két file-t összefésüljük egy-egy elemet véve mindkét file-ból. Az eredményfile-ban már lesz a futamhossz.(esetleg a legutolsó rövidebb lehet). Ezt ismételgetjük a teljes rendezettségig mindig duplázva értékét. Legyen a rekordok száma . Egy menetben rekordmozgás van a szétdobásnál és az összefésülésnél. A menetek száma legfeljebb .

Az időigény: .

Külső tárak rendezésének gyorsítása

Az nem javítható az összehasonlítások miatt. A szorzó konstansokat lehet csökkenteni.