Gyorsrendezés (algoritmus)

A Programozás Wiki wikiből
(Gyorsrendezés szócikkből átirányítva)

A gyorsrendezés egy gyakran használt, hatékony rendezési algoritmus. Futásideje átlagos esetben n*log n, legrosszabb esetben n^2.

A gyorsrendezés az "oszd meg és uralkodj" elven alapul: a feladatot kisebb hasonló részfeladatokra bontja, amíg azok megoldása triviálissá nem válik. A gyorsrendezés lépései:

  1. Kiválasztunk egy tetszőleges elemet, amit vezérelemnek nevezünk.
  2. Úgy rendezzük át a tömbelemeket, hogy a vezérelemnél kisebb elemek előre kerüljenek, a nagyobbak hátra. (A vezérelemmel egyenlő elemek vagy a kisebbekkel, vagy a nagyobbakkal kerülnek egy csoportba, vagy külön csoportot is alkothatnak középen, a kisebb, és nagyobb elemek csoportja között.)
  3. Az első, és az hátsó csoportot ugyanezzel az eljárással rendezzük.

Mindhárom lépésben vannak nyitva hagyott kérdések, ezért a gyorsrendezést több módon lehet implementálni.

Az első lépés nem határozza meg, milyen stratégiával válasszuk a vezérelemet. Az algoritmus akkor a leghatékonyabb, ha a választott vezérelemmel két egyenlő részre tudjuk bontani a tömböt. A legrosszabb eset az, ha a választott elem éppen a legnagyobb vagy a legkisebb. Az egyszerű implementációk általában az első vagy a középső elemet választják. Ha véletlenszerűen választjuk a vezérelemet, jelentősen csökken annak az esélye, hogy négyzetes időben fusson az algoritmus.

A második lépést legegyszerűbben egy segédtömb használatával tudjuk megoldani: a segédtömb elejére másoljuk a vezérelemnél kisebb elemeket, majd bemásoljuk a vezérelemet, végül bemásoljuk a maradék elemeket. A módszer hátránya a kétszeres memóriaigény és a rossz cache kihasználás. Lehetséges a második lépést helyben is megoldani.

A harmadik lépést nem feltétlenül kell gyorsrendezéssel implementálni; tetszőleges rendezési algoritmus használható. Az algoritmust elméletben úgy szokták tárgyalni, hogy a triviális (0 vagy 1 elemű) tömböket nem módosítjuk, a többire pedig mindig rekurzívan gyorsrendezést alkalmazunk. A gyakorlatban szokásos megoldás ezzel szemben az, hogy egy bizonyos méretkorlát alatt minimumkiválasztásos vagy beszúrásos rendezést alkalmazunk. (Az ideális méretkorlát az adott architektúrától függ.)

Az algoritmus további előnye a könnyű párhuzamosíthatóság: a harmadik lépésben történő két rendezés egymástól független, ezért párhuzamosan is végrehajtható. Ha ezen rendezések maguk is a gyorsrendezés algoritmusát használják, ők maguk is két-két párhuzamosítható rendezésre "bomlanak szét", és minden lépésben kétszer annyi részfeladatot kapunk. Ezeket a feladatokat tetszőlegesen oszthatjuk szét a végrehajtó egységeink között.

Példák[szerkesztés]

Példa C-ben

Példa C++-ben

Példa Go-ban