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

Lineáris idejű particionálás

Google Osztályterem
A gyorsrendezésben a tényleges munka az oszd meg lépésben történik, ami a résztömbből kiválasztott vezérelem mentén particionálja az array[p..r] résztömb többi elemét. A résztömb bármelyik elemét választhatjuk vezérelemnek, de a particionálás implementálását megkönnyíti, ha a jobb szélső elemet, A[r]-t választjuk.
Miután kiválasztottuk a vezérelemet, úgy particionáljuk a résztömböt, hogy jobbról balra végigmegyünk, és összehasonlítjuk az elemeket a vezérelemmel. Két indexet vezetünk be, q-t és j-t, amivel a résztömböt négy részre osztjuk. A q változónevet azért használjuk, mert az végül majd a vezérelemre fog mutatni. A j egy szokványos futóindex, amit a végén úgyis eldobunk.
  • Az array[p..q-1] elemei alkotják a „K csoportot”, amelybe azok az elemek tartoznak, melyekről tudjuk, hogy azok a vezérelemnél kisebbek vagy egyenlőek.
  • Az array[q..j-1] elemei alkotják az „N csoportot”, amelybe azok az elemek tartoznak, melyekről tudjuk, hogy azok a vezérelemnél nagyobbak.
  • Az array[j..r-1] elemei alkotják az „I csoportot”, melybe azok az elemek tartoznak, amelyeknek a vezérelemhez viszonyított nagyságrendje egyenlőre ismeretlen, mert még nem hasonlítottuk őket össze.
  • Végül array[r], a vezérelem alkotja a „V csoportot”.
q és j kezdeti értéke p. Az egyes lépésekben összehasonlítjuk A[j]-t, az I csoport bal szélső elemét a vezérelemmel. Ha A[j] nagyobb, mint a vezérelem, akkor megnöveljük j-t, ezzel az N és az I csoportokat elválasztó vonal eggyel jobbra csúszik:
Az ábra a résztömb particionálás egy lépését mutatja be. A résztömb a p indexnél kezdődik, négy elem tartozik az N csoporthoz, ezután jön a q index, majd hat elem az N csoportban, a j index, ezután öt elem az I csoportban, végül az r index. A lépést követően a résztömb majdnem változatlan, de az N csoportban hét elem lesz, az I csoportban négy elem lesz, és a j index az I csoport első elemére mutat.
Ha viszont az A[j] kisebb, vagy egyenlő a vezérelemnél, akkor kicseréljük A[j]-t és A[q]-t (az N csoport bal szélső elemét), megnöveljükj-t és q-t is, ezzel a K és N csoportokat, valamint az N és I csoportokat elválasztó vonalat eggyel jobbra toljuk:
Az ábra a résztömb particionálás egy lépését mutatja be. A résztömb a p indexnél kezdődik, négy elem tartozik az K csoporthoz, ezután jön a q index, majd hat elem az N csoportban, a j index, ezután öt elem az I csoportban, végül az r index. A lépést követően a résztömbben az N csoportban öt elem lesz (az utolsó elemben a korábban a j indexen levő érték lesz), az I csoportban négy elem lesz, és a j index az I csoport első elemére mutat.
Amikor elérkezünk a vezérelemhez, addigra az I csoport kiürül. Kicseréljük a vezérelemet az N csoport bal szélső elemével: megcseréljük A[r]-t és A[q]-t. Ez a csere a vezérelemet a K és N csoportok közé helyezi, és ez akkor is jó eredményt ad, ha akár a K, akár az N csoport üres.
Az ezt az elvet megvalósító partition függvény azt a q indexet is visszaadja, ahova a vezérelemet végül elhelyezte, így a hívó quicksort függvény azt is tudni fogja, hol vannak a partíciók.
Megmutatjuk az array[4..9]résztömbjének [12, 7, 14, 9, 10, 11] particionálási lépéseit :
n elemű résztömb particionálása Θ(n) időt vesz igénybe. Minden A[j] elemet össze kell hasonlítani egyszer a vezérelemmel. Az A[j]-t vagy ki kell cserélni A[q]-val, vagy nem; q-t vagy inkrementáljuk, vagy nem; j-t mindig inkrementáljuk. A résztömb minden egyes elemére végrehajtott programsorok száma konstans. Mivel a résztömbnek n eleme van, a particionálás futásideje lineáris: Θ(n).
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.