Fő tartalom
Számítástudomány
Tantárgy/kurzus: Számítástudomány > 1. témakör
9. lecke: GyorsrendezésA gyorsrendezés áttekintése
Hasonlóan az összefésülő rendezéshez, a gyorsrendezés is az oszd meg és uralkodj algoritmust használja, úgyhogy az is rekurzív algoritmus. A gyorsrendezés másképpen használja az oszd meg és uralkodj algoritmust, mint az összefésülő rendezés. Az összefésülő rendezésben az oszd meg lépés jóformán semmit se csinál, a munka lényegét az összefésülés lépésben végezzük. A gyorsrendezés ennek pont az ellenkezője: a nagy munkát az oszd meg lépésben végzi. Igazándiból az összefésülés lépésben egyáltalán semmi se történik.
A gyorsrendezés több ponton is eltér az összefésülő rendezéstől. A gyorsrendezés helyben rendez. A legrosszabb esetben a futásideje ugyanolyan rossz, mint a minimumkiválasztásos rendezésé és a beszúró rendezésé: . De az átlagos futásidő megegyezik az összefésülő rendezés futásidejével: .
Akkor viszont minek bajlódunk a gyorsrendezéssel, ha az összefésülő rendezés legalább olyan jó? Azért, mert a Θ jelölésben elrejtett konstans tényező miatt a gyorsrendezés egészen jó eredményeket produkál. Gyakorlatban a gyorsrendezés sokkal jobban teljesít, mint az összefésülő rendezés, és szignifikánsan jobb teljesítményt nyújt a minimumkiválasztásos és a beszúró rendezésnél.
Így használja a gyorsrendezés az oszd meg és uralkodj elvet. Hasonlóan az összefésülő rendezéshez, az
array[p..r]
résztömböt rendezzük, ahol a kiinduló résztömb array[0..n-1]
.- Oszd meg úgy, hogy kiválasztod az
array[p..r]
résztömb valamelyik elemét. Ezt az elemet vezérelemnek fogjuk hívni.
Rendezd át úgy az
array[p..r]
résztömb elemeit, hogy az array[p..r]
résztömb minden, a vezérelemnél kisebb, vagy egyenlő eleme a vezérelemtől balra, minden nagyobb eleme attól jobbra legyen. Ezt az eljárást particionálásnak hívjuk. Ezen a ponton nem érdekes, hogy a vezérelemtől jobbra és balra elhelyezkedő elemek egymáshoz képest milyen sorrendben helyezkednek el. Csak az számít itt, hogy minden egyes elem a vezérelem megfelelő oldalára kerüljön.Az egyszerűség kedvéért mindig a résztömb jobb szélső elemét, `array[r]`-t fogjuk vezérelemnek választani. Például, ha a résztömbünk [9, 7, 5, 11, 12, 2, 14, 3, 10, 6], akkor a vezérelem 6 lesz. A megosztás után a résztömb elképzelhető, hogy valahogy így fog kinézni: [5, 2, 3, 6, 12, 7, 14, 9, 10, 11]. Legyen `q` a vezérelem indexe a megosztás után.
- Uralkodj úgy, hogy rekurzívan rendezed az
array[p..q-1]
-t (a vezérelem bal oldalán található összes elemet, melyek kisebbek, vagy egyenlőek a vezérelemnél), és azarray[q+1..r]
-t (a vezérelem jobb oldalán található összes elemet, melyek nagyobbak, mint a vezérelem). - Fésüld össze úgy, hogy nem csinálsz semmit. Miután az uralkodj lépés rekurzív rendezése befejeződik, már készen vagyunk. Miért? A vezérelem bal oldalán levő összes elem az
array[p..q-1]
-ben kisebb, vagy egyenlő, mint a vezérelem, és már rendezve is vannak; a vezérelem jobb oldalán levő összes elem azarray[q+1..r]
-ben nagyobb, mint a vezérelem, és már rendezve is vannak. Azarray[p..r]
így mindenképpen rendezett!Gondolj a példánkra! Miután rekurzívan rendeztük a vezérelem bal és jobb oldalán található résztömböket, a vezérelem bal oldalán a [2, 3, 5] résztömb lesz, a jobb oldalán pedig a [7, 9, 10, 11, 12, 14] résztömb. Tehát a [2, 3, 5] résztömb után következik a 6, majd [7, 9, 10, 11, 12, 14] jön. A résztömb már rendezett.
Az alapeset a két elemnél rövidebb résztömb, ugyanúgy, mint az összefésülő rendezésnél. Az összefésülő rendezésnél soha nem fordul elő olyan résztömb, amelynek nincs eleme, de a gyorsrendezésnél ez előfordulhat akkor, ha a résztömb minden eleme kisebb, vagy minden eleme nagyobb, mint a vezérelem.
Menjünk vissza az uralkodj lépésre, és lépésenként nézzük meg a résztömbök rekurzív rendezését! Az első megosztás után a két résztömb [5, 2, 3] és [12, 7, 14, 9, 10, 11], a vezérelem 6.
Az [5, 2, 3] résztömb rendezéséhez 3-at választjuk vezérelemnek. A particionálás után [2, 3, 5]-öt kapunk. A [2] résztömb a vezérelem balján alapeset a rekurzióban, ugyanúgy, mint az [5] a vezérelem jobb oldalán.
A [12, 7, 14, 9, 10, 11] résztömb rendezéséhez 11-t választjuk vezérelemnek. A megosztás után a vezérelem bal oldalára [7, 9, 10], jobb oldalára [12, 14] kerül. Ezután a résztömböket rendezzük,
ennek eredménye [7, 9, 10], majd 11, végül [12, 14] lesz.
A teljes gyorsrendezés folyamata így néz ki. A kék színnel jelölt elemek már voltak vezérelemek egy korábbi rekurzív hívás során, úgyhogy ezeket az értékeket már nem kell megvizsgálni, vagy arrébb helyezni:
Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tanmenetfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.