Gyorsrendezés – még egy rekurzív rendezés

A gyorsrendezés (quick sort) egy rekurzív rendezőalgoritmus. Lényege: egy elemet vezérelemnek választva két részre osztjuk a tömböt: a vezérelemnél kisebbekre és nagyobbakra. Ha a kicsiket a tömb elejére, a nagyokat a tömb végére tesszük, azzal közelebb kerülünk a rendezett állapothoz.

A gyorsrendezés jól optimalizálható, ha számokat kell rendezni. Mivel minden összehasonlítás a vezérelemet vizsgálja, azt körönként csak egyszer kell kiolvasni a memóriából. (Ez persze a C kódban nem látszik, csak a fordító által optimalizáltban.) C. A. R. Hoare angol programozó, matematikus. Legismertebb eredménye ez az algoritmus, amelyet 26 évesen dolgozott ki.

A gyorsrendezés az „oszd meg és uralkodj” elven működik. Lépései a következők:

• Kiválasztunk a tömbből egy tetszőleges elemet. Ez lesz az ún. vezérelem (pivot).
• Az ennél kisebbeket a tömb elejére, az ennél nagyobbakat a tömb végére rendezzük. A vezérelemmel megegyező elemek mehetnek bármelyik oldalra.
• Ezután az így keletkező két tömbrészletet külön rendezzük, az algoritmus rekurzív hívásával.

start következő folyamatos

Érdemes megfigyelni a következőt: ha a vezérelem elé rendeztük a kisebbeket, mögé a nagyobbakat, az azt jelenti, hogy a vezérelem már a végleges helyére kerül. Ugyanis ha nála kisebből van emennyi (előtte), nála nagyobból meg amannyi (utána), akkor ezek a számok egyben a vezérelem helyét is meghatározzák. Hiszen ezek (emennyi és amannyi) nem fognak már változni.

Az algoritmus hatékonysága azon múlik, hogy sikerül-e jó vezérelemet választani. Akkor lehet minden lépésben a kisebbekre és nagyobbakra szedett tömbrészeket egyenlő nagyságúvá tenni (vagyis felezni a tömböt), ha a vezérelem éppen a tömb mediánja, azaz a rendezett tömb középső eleme. Sajnos a mediánt nem tudjuk megmondani, hiszen ahhoz rendezve kellene legyen a tömb… Ezért leginkább azt szokták csinálni, hogy találomra választanak egyet, akár éppen az elsőt vezérelemnek, és kész. Ez persze nem optimális minden esetben. Pár „start” gomb klikkelés után ez látszik is, ha kijön egy olyan tömb, ahol 1 vagy 9 az első elem. Ilyenkor az első körben szinte semmi nem történik. Emiatt van az, hogy bár átlagos esetben ez az algoritmus Θ(n log n) időben tud teljesíteni, de legrosszabb esetben ugyanúgy O(n²) időben fut le, mint egy buborékrendezés.

A szétválogatás működésének lényege: a tömb két végéről indulnak indexek. Megkeressük balról az első pirosat, jobbról kéket, és megcseréljük őket. Ezt folytatjuk, amíg a két index nem találkozik.

start következő

Kicsit részletesebben:

1. Indítunk két indexet, egyiket a tömb elejéről (bal), másikat a végéről (jobb).
2. Balt addig növeljük, amíg kék golyóra mutat. Így találunk egy piros golyót.
3. Jobbat addig csökkentjük, amíg piros golyóra mutat. Így
4. Megcseréljük a talált pirosat a kékkel, és így folytatjuk, amíg a két index „össze nem ér”.

Minden csere után természetesen növelhetjük a balt és csökkenthetjük a jobbat eggyel, hiszen a csere hatására a bal index alá kék, a jobb index alá pedig piros golyó kerül. Fontos, hogy a keresések során is figyeljük, hogy nem értek-e össze az indexek; ez előfordulhat ugyanis bármelyik pillanatban. (Ezzel azt is ellenőrizzük, hogy nem érünk-e a tömb végére valamelyik indexszel. Az is lehetséges, ha a tömb csak kék vagy csak piros golyót tartalmaz.)

enum golyo { kek, piros };

void szetvalogat(enum golyo *tomb, int meret) {
   int bal = 0, jobb = meret-1;

   while (bal < jobb) {
      while (bal < jobb && tomb[bal] != piros)  // pirosat keres
         ++bal;
      while (bal < jobb && tomb[jobb] != kek)   // kéket keres
         --jobb;

      if (bal < jobb) {
         enum golyo temp = tomb[bal];   // csere
         tomb[bal] = tomb[jobb];
         tomb[jobb] = temp;
         ++bal;
         --jobb;        // egyből a következőkre
      }
   }
}

Vagyis pl. a kereső ciklusok megállhatnak így:

Ha megcseréljük a tomb[bal] és a tomb[jobb] elemet:

Akkor a csere után a két indexet gondolkodás nélkül növelhetjük és csökkenthetjük:

És innen folytatjuk megint piros-kék kereséssel.

void gyorsrendez(double *tomb, int min, int max) {
   double vezer = tomb[(min+max)/2]; // vezérelem: középső
   int i = min, j = max;
   while (i <= j) {                  // piros/kék válogatás
      while (tomb[i] < vezer) ++i;
      while (tomb[j] > vezer) --j;
      if (i <= j) {
         double tmp = tomb[i];
         tomb[i] = tomb[j];
         tomb[j] = tmp;
         ++i;
         --j;
      }
   }

   if (min < j) gyorsrendez(tomb, min, j); // rekurzió
   if (i < max) gyorsrendez(tomb, i, max);
}

Az algoritmus részei: a while (i <= j) ciklus végzi a szétválogatást; utána pedig az utolsó két sorban láthatók a rekurzív hívások, amelyek rendezik a tömb így keletkezett két részét.

Az i<=j ciklus végefelé az i és a j index is a már helyre került vezérelemnél áll. A belső, piros-kék keresős ciklusok megállnak a megtalált vezérelemnél is, hiszen elem<vezér és elem>vezér kifejezések a feltételeik. (Tehát a pirosat kereső ciklusnak a vezérelem pirosnak számít, a kéket kereső ciklusnak a vezérelem kéknek számít. Ha a vezérelem elöl van, akkor egy cserében hátrébb kerül, ha hátul van, akkor egy cserében előrébb kerül. Előfordulhat, hogy ide-oda pattog, de végül középre fog kerülni.) A ciklus futása után egy ilyen állapot lesz a tömbben:

Ezután az i++ és j-- utasítással még módosítjuk az indexeket (lásd a szétválogatási feladatot). Így i és j a rendezendő két részintervallum széleit is jelzik, és az eddigiektől eltérően j<i igaz:

Ezért van az, hogy a két rendezendő tömbrészlet a [min,j] és az [i,max] indexű részek.

Az előzőektől eltérően ennek a függvénynek nem a tömb méretét kell megadni, hanem a rendezendő intervallum alsó és felső határát. De ez nem gond, hiszen egy egysoros függvénnyel ugyanolyan formában használhatjuk ezt is:

void gyorsrendez_indit(double *tomb, int meret) {
   gyorsrendez(tomb, 0, meret-1);
}

A fenti kód a gyorsrendezésnek csak egy variációja. Nem az igazi algoritmus, hanem egy olyan változat, amelyen keresztül könnyű megérteni a működést. Ugyanis nem igaz rá, hogy egy körben az aktuális vezérelem a helyére kerül. Arról van szó, hogy ha a vezérelem két oldalán keresett nála nagyobb, illetve kisebb elemek nem egyszerre fogynak el, akkor a vezérelem vándorolni kezd és az i, j mutatók csak az egyik oldalára kerülnek. Ezért pedig az aktuális vezérelem csak egy későbbi függvényhívásnál kerül helyre.

Ezt az okozza, hogy a szétválogatásban nem csak kékek és pirosak vannak, hanem van a vezérelem, a sárga is. Azt a sima kék-piros szétválogatásnál elvileg kéknek is és pirosnak is (vagy: kéknek sem és pirosnak sem) kellene tekinteni. Ideális esetben ide-oda pingpongozna a két ciklus a vezérelemmel, úgy tudna az középen megérkezni.

Viszont ennek a megvalósítása nem triviális. Ehhez az kellene, hogy a csere után ne azt mondjuk, hogy ++i és --j, hanem hogy if (tomb[i]!=vezer) ++i;, és if (tomb[j]!=vezer) --j;, hogy a pingpongozás megvalósulhasson (egymás után kétszer is elmozdíthassuk ugyanazt az elemet). Ez viszont végtelen ciklust eredményezhetne akkor, ha a vezérelem olyan értékű, amiből kettő van.

Tehát a szétválogatás (particionálás) a fenti kódban nem tökéletes. De a gyorsrendezéshez elegendő, mert a szétválogatás által hagyott hibát a későbbi rendezési lépések kijavítják.