5.2. Oszd meg és uralkodj!

A politikában használatos elvnek az informatikában is hasznát vehetjük. A módszer alapelve a következő:

(1) Felosztjuk a problémát több alproblémára.

(2) Uralkodunk az alproblémákon.

– Ha az alprobléma mérete kicsi, akkor azt közvetlenül megoldjuk.

- Egyébként rekurzív megoldást alkalmazunk, azaz az alproblémákat újra az oszd meg és uralkodj elvét alkalmazva oldjuk meg.

(3) Összevonjuk az alproblémák megoldásait az eredeti probléma megoldásává.

5.2.1. Összefésülő rendezés

Az összefésülő rendezés is ezt az elvet követi A lépések ebben az esetben a következők:

(1) Az n elemű sorozatot felosztja két n 2 elemű alsorozatra.

(2) A két alsorozatot összefésülő rendezéssel rekurzívan rendezi.

(3) Összefésüli a két sorozatot, létrehozva a rendezett választ.

5.2. példa - 5. példa

Rendezzük az alábbi számsorozatot az összefésülő rendezéssel!

Először is fel kell bontani a sorozatot két négyes csoportra, s ezeket kell különkülön rendezni. Ehhez a négyeseket kettesekre kell bontani, s azokat rendezni. Miután továbbra is összefésülő rendezést használunk, a ketteseket is egyesekre bontjuk. Egy szám magában már rendezett, így elkezdhetjük a harmadik lépést, az összefésülést. Itt a rendezett sorozatok első elemeit kell figyelni, s a kettő közül a kisebbiket kell egy másik tárolóban elhelyezni, s törölni a sorozatból. Ha mindkét sorozat elfogy, a másik tárolóban a két sorozat összefésültje található. Így fésülhet őek össze az egyesek, majd a kettesek, s végül a négyesek.


A ofesulo.htm állomány tartalmazza azt a programot, amely egy véletlen módon generált számsorozatra végrehajtja az összefésülő rendezést. A program különböző szinekkel jelzi a két részsorozatot, s az összefésült sorozatokat.

A módszer elemzése. Ha T(n) jelöli a probléma futási idejét, D(n) a probléma alproblémákra bontásának idejét, C(n) a alproblémák megoldásának összevonását, a darab alproblémára bontottuk az eredeti problémát, és egy alprobléma mérete az eredeti probléma méretének 1/b része, valamint c jelöli a triviális feladatok megoldásának idejét, akkor a következő összefüggést írhatjuk fel:

5.. egyenlet -


Összefésülő rendezés esetén

Ha a d és c konstansok közel egyformák, belátható, hogy

5.. egyenlet -


5.2.2. Gyorsrendezés

A gyorsrendezés is az „oszd meg és uralkodj” elvet követi. Ehhez az aktuális elemeket két csoportra bontja úgy, hogy az első csoport elemei mind kisebbek a második csoport elemeinél, majd ezeket külön-külön rendezzük.

A FELOSZT rutin a megadott tömb két indexe közti elemeket válogatja szét az alapján, hogy a második index által mutatott elemnél (x) kisebbek, vagy nagyobbak- e. A kisebb elemeket a résztömb elejére, a nagyobb elemeket a résztömb végére csoportosítja.

Function FELOSZT(A,p,r) 
Input: Az A tömb és két indexe, ahol p ≤ r 
Output: q, az az index, ahova az r indexnél található elem került. 
Eredmény: Az A tömb elemeit átcsoportosítja úgy, hogy a p-től q-ig terjedő elemek kisebbek, mint az q-től r-ig terjedő elemek 
1 x = A[r] 
2 i = p − 1 
3 for j = p to r − 1 do 
4    if A[j] ≤= x then 
5       i++ 
6       A[i] és A[j] cseréje 
7    endif 
8 endfor 
9 A[i + 1] és A[r] cseréje 
10 return i+1 

A következő táblázatban az arany színű számok azok, melyekről kiderült, hogy a második index által mutatott számnál kisebbek, és világoskékek a nála nagyobbak.

A példánkban p = 1 és r = 6.

A FELOSZT rutin az „oszd meg és uralkodj elvéből” a felosztást végzi. Mivel a q index előtt a q indexnél szereplő számnál kisebb, mögötte pedig nagyobb számok szerepelnek, a harmadik lépésre, a megoldások összevonására nincs szükség. Egyedül a rekurzív függvényhívások hiányoznak. Ezt a GYORSRENDEZÉS rutin valósítja meg. Mivel ez a rutin a megadott két index közötti részt rendezi, az A tömb egészének rendezéséhez a rutint a GYORSRENDEZÉS(A,1,A.hossz) módon kell indítani.

Procedure GYORSRENDEZÉS(A,p,r) 
Input: A tömb, s a rendezendő résztömböt meghatározó indexek 
Eredmény: a tömb megadott indexei közti részt nagyság szerint rendezi 
1 if p ≤ r then 
2    q = FELOSZT(A,p,r) 
3    GYORSRENDEZÉS(A,p,q-1) 
4    GYORSRENDEZÉS(A,q+1,r) 
5 endif 

A gyorsrendezésben a partícionálásnak más módszerei is ismertek, például a két végéről haladunk a sorozatnak, elől/hátul átlépdelünk a kijelölt elemnél kisebb/nagyobb elemeken, majd ha nem ért össze a két mutató, kicseréljük a két mutató által jelölt elemeket, s folytatjuk az átlépdelést.

A módszer elemzése A gyorsrendezés hatékonysága azon múlik, hogy felosztás során mennyire egyforma méretű alsorozatokat kapunk. A legrosszabb esetben a sorozat rendezett, ekkor a módszer négyzetes függvénye a hossznak. Legjobb esetben O(n ln(n)) lesz a futás bonyolultsága. Mivel rendezett, illetve közel rendezett esetekben a legrosszabb futási eredményeket kapjuk, ekkor szokásos a sorozat középső elemét választani A[r] helyett. Általános esetben pedig a sorozat egy véletlen elemét.

A gyors.htm állomány tartalmazza azt a programot, amely egy véletlen módon generált számsorozatra végrehajtja a gyorsrendezést. A vgyors.htm állomány ennek a programnak azt a változatát tartalmazza, amely egy véletlenül választott elem alapján osztja szét a sorozatokat.