If you're seeing this message, it means we're having trouble loading external resources on our website.

Ha webszűrőt használsz, győződj meg róla, hogy a *.kastatic.org és a *.kasandbox.org nincsenek blokkolva.

Fő tartalom

Tantárgy/kurzus: Számítástudomány > 1. témakör

9. lecke: Gyorsrendezés
Informatika
Számítástudomány
Algoritmusok
Gyorsrendezés
© 2024 Khan AcademyFelhasználási feltételekAdatkezelési tájékoztatóSüti figyelmeztetés

A gyorsrendezés áttekintése

Google Osztályterem
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é: Θ(n2). De az átlagos futásidő megegyezik az összefésülő rendezés futásidejével: Θ(nlog2⁡n).
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].
  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.
  1. 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 az array[q+1..r]-t (a vezérelem jobb oldalán található összes elemet, melyek nagyobbak, mint a vezérelem).
  2. 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 az array[q+1..r]-ben nagyobb, mint a vezérelem, és már rendezve is vannak. Az array[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:
A gyorsrendezés folyamatát bemutató ábra.
  1. A kiinduló tömb elemei [9, 7, 5, 11, 12, 2, 14, 3, 10, 6], a p index az első, az r index az utolsó elemre mutat.
  2. Most a tömb elemeinek sorrendje [5, 2, 3, 6, 12, 7, 14, 9, 10, 11]. A tömb q indexe a negyedik elemre mutat, aminek értéke 6.
  3. Most a tömb elemeinek sorrendje [2, 3, 5, 6, 7, 9, 10, 11, 14, 12]. A tömbnek most több p, q, és r indexe van. Az első p az első elemre mutat, az első q a második elemre mutat, az első r a harmadik elemre mutat. A második p az ötödik elemre mutat, a második q a nyolcadik elemre mutat, és a második p az utolsó elemre mutat.
  4. Most a tömb elemeinek sorrendje [2, 3, 5, 6, 7, 9, 10, 11, 12, 14]. Az első p és r pár az első elemre mutat, a második p és r pár a harmadik elemre mutat. A harmadik p az ötödik elemre mutat, a q és a harmadik r a hetedik elemre mutat. A negyedik p és egy q a kilencedik elemre mutat, és a negyedik r az utolsó elemre mutat.
  5. Most a tömb elemeinek sorrendje [2, 3, 5, 6, 7, 9, 10, 11, 12, 14]. Az első p az ötödik elemre mutat, az első q és az első r a hatodik elemre mutat. Egy p és r pár az utolsó elemre mutat.
  6. Most a tömb elemeinek sorrendje még mindig [2, 3, 5, 6, 7, 9, 10, 11, 12, 14]. Egyetlen p és r pár az ötödik elemre mutat.
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?

Jelentkezz be
Még nincs hozzászólás.
Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.