6. Előadás - Rendező algoritmusok

Rendező algoritmusok

A \(\rho\) (részben) rendezési reláció tulajdonságai:

  • reflexív: \(a \rho a, \forall a \in A\)

  • antiszimmetrikus: \(a \rho b\) és \(b \rho a\) esetén \(a = b\)

  • tranzitív: \(a \rho b\) és \(b \rho c\) esetén \(a \rho c\)

A teljes rendezés esetében elvárjuk azt is, hogy a halmaz bármely két kiválasztott eleme között legyen reláció.

Beszúrásos rendezés

Az algoritmus működése

  • Kiindulunk egy üres eredmény sorozatból.

  • Az eredeti tömb elemeit sorban beszúrjuk úgy, hogy mindig rendezett sorozatot kapjunk.

  • A beszúrás mindig a tömb végétől kezdve történik. (A tömb elejétől kezdve költségesebb lenne.)

\(\rhd\) Egy 9 elemű példán nézzük meg az algoritmus működését!

Párhuzamosítás

Megpróbálhatunk beszúrni úgy elemeket, hogy a korábbi beszúrások még tartanak.

  • A beszúrást végző iterátorok között megfelelő távolságnak kell lenni.

  • A beszúrandó elemeket rendezni kell, és a kisebb értékeket kell először beszúrni. (Ez egy független rendezési feladat, melyhez szintén használható például a beszúró rendezés.)

  • Elvi szinten a megoldás működik, de szinkron működést feltételez.

  • Szálak szintjén a szinkronizációs költség aránytalanul nagy.

\(\rhd\) Egy 9 elemű példán vizsgáljuk meg 3 iterátorral az algoritmus működését!

\(\rhd\) Rajzoljuk fel a Gantt diagramot az összehasonlítás és csere műveletekkel!

Minimumkiválasztásos rendezés

Az algoritmus működése

  • Kiindulunk egy üres eredmény sorozatból.

  • A bemeneti sorozatunknak megkeressük a minimumát.

  • Ezt beszúrjuk az eredménysorozat végére.

  • Az előző két lépést addig ismételjük, amíg el nem fogynak az elemek a bemeneti sorozatból.

\(\rhd\) Egy 5 elemű példán nézzük meg az algoritmus működését!

Párhuzamosítás

(I.) A minimum keresést párhuzamosíthatjuk.

  • Tetszőlegesen sok számítási egység esetében a keresés \(\log_2 (n)\) időre csökkenthető.

  • A teljes számítási idő így:

\[T(n) = \displaystyle \sum_{i=1}^{n} \log_2(i).\]

  • Ez ugyan gyorsabb lesz, mint az eredeti \(T(n) = \Theta(n^2)\) időbonyolultság, de nem elég hatékony így sem (a következőkben bemutatásra kerülő algoritmusokhoz képest).

\(\rhd\) Egy 5 elemű példán nézzük meg az algoritmus működését!

\(\rhd\) Rajzoljuk fel a Gantt diagramot az összehasonlításokra nézve, és számítsuk ki a költség, munka, gyorsítás és hatékonyság értékét! (Feltételezzük, hogy tetszőleges sok számítási egységünk lehet!)

(II.) Csoportokat képezhetünk

A négyzetes rendezés analógiájára elképzelhető a következő algoritmus.

  • Tegyük fel, hogy van \(p\) darab számítási egységünk.

  • Osszuk fel a rendezendő tömbünket \(p - 1\) részre.

  • A \(p - 1\) számú számítási egységgel határozzuk meg minden résztömbnek a saját minimumát.

  • A \(p.\) számítási egységnek allokáljunk egy \(p - 1\) méretű segédtömböt, amelybe belekerülnek a csoportonkénti minimumok.

  • Kezdjük el kiszámolni a résztömbökben maradt következő minimumot. Közben számítsuk ki a segédtömb minimumát.

  • A kapott minimumot írjuk az eredménytömb végére.

  • Amint egy minimumot kivettünk a segédtömbből, írjuk be a helyére a hozzá tartozó csoport következő minimum értékét. (Itt előfordulhat, hogy a \(p.\) számítási egységnek várni kell a minimumérték meghatározására.)

  • Folytassuk addig az eljárást, amíg minden érték el nem fogy a csoportokból.

A számítás akkor tud hatékony lenni, hogy ha a minimumértékek mindig más csoportokból kerülnek ki. Az algoritmus egyik legrosszabb esete a rendezett tömb.

Összefésülés

Két bemeneti tömbös változat

\[\begin{split}\begin{align*} &\text{MERGE_ARRAYS}(@A, @B, @C) \\ &\text{// Input}: A \in \mathrm{R}^n \\ &//\quad\quad\quad\, B \in \mathrm{R}^m \\ &\text{// Output}: C \in \mathrm{R}^{n+m} \\ &i \leftarrow 1, j \leftarrow 1, k \leftarrow 1\\ &\text{WHILE }i \leq n\text{ AND }j \leq m\text{ DO}\\ &\quad \text{IF }a_i \leq b_j\\ &\quad\quad \text{THEN }c_k \leftarrow a_i\\ &\quad\quad\quad\quad\quad i \leftarrow i + 1\\ &\quad\quad \text{ELSE }c_k \leftarrow b_j\\ &\quad\quad\quad\quad\quad j \leftarrow j + 1\\ &\quad k \leftarrow k + 1\\ &\text{WHILE }i \leq n\text{ DO}\\ &\quad\quad\quad c_k \leftarrow a_i\\ &\quad\quad\quad i \leftarrow i + 1\\ &\quad\quad\quad k \leftarrow k + 1\\ &\text{WHILE }j \leq m\text{ DO}\\ &\quad\quad\quad c_k \leftarrow b_j\\ &\quad\quad\quad j \leftarrow j + 1\\ &\quad\quad\quad k \leftarrow k + 1\\ &\text{RETURN}(C) \\ \end{align*}\end{split}\]

Egy bemeneti tömbös változat

\[\begin{split}\begin{align*} &\text{MERGE}(@A, p, q, r) \\ &\text{// Input}: A, \text{sorozat} \\ &//\quad\quad\quad\, p, q, r \in \mathrm{N}, p \leq q \leq r \\ &\text{// Output}: A, \text{rendezett sorozat} \\ &X \leftarrow \text{COPY}(A)\\ &i \leftarrow 1, j \leftarrow q + 1, k \leftarrow 1\\ &\text{WHILE }i \leq q\text{ AND }j \leq r\text{ DO}\\ &\quad \text{IF }x_i \leq x_j\\ &\quad\quad \text{THEN }a_k \leftarrow x_i\\ &\quad\quad\quad\quad\quad i \leftarrow i + 1\\ &\quad\quad \text{ELSE }a_k \leftarrow x_j\\ &\quad\quad\quad\quad\quad j \leftarrow j + 1\\ &\quad k \leftarrow k + 1\\ &\text{WHILE }i \leq q\text{ DO}\\ &\quad\quad\quad a_k \leftarrow x_i\\ &\quad\quad\quad i \leftarrow i + 1\\ &\quad\quad\quad k \leftarrow k + 1\\ &\text{WHILE }j \leq r\text{ DO}\\ &\quad\quad\quad a_k \leftarrow x_j\\ &\quad\quad\quad j \leftarrow j + 1\\ &\quad\quad\quad k \leftarrow k + 1\\ &\text{RETURN}(A) \\ \end{align*}\end{split}\]

\(\rhd\) Vizsgáljuk meg az algoritmus működését egy 12 elemű példán!

\(\rhd\) Határozzuk meg az elvégzett összehasonlítások számát!

Batcher-féle páros-páratlan összefésülés

Tegyük fel, hogy adott egy \(A\) és egy \(B\) sorozat, amit össze szeretnénk fésülni.

\[\begin{split}\begin{align*} A &= \{a_1, a_2, a_3, \ldots\}\\ B &= \{b_1, b_2, b_3, \ldots\}\\ \end{align*}\end{split}\]

Bontsuk fel ezeket külön tömbökre az indexek paritása szerint!

\[\begin{split}\begin{align*} A_1 &= \{a_1, a_3, a_5, \ldots\}\\ A_2 &= \{a_2, a_4, a_6, \ldots\}\\ B_1 &= \{b_1, b_3, b_5, \ldots\}\\ B_2 &= \{b_2, b_4, b_6, \ldots\}\\ \end{align*}\end{split}\]

Fésüljük össze ezeket az \(U\) és \(V\) sorozatokba:

\[\begin{split}\begin{align*} &A_1, B_2 \rightarrow U \\ &A_2, B_1 \rightarrow V \\ \end{align*}\end{split}\]

A \(C\) eredménysorozatot az \(U\) és \(V\) sorozatok összefésülésével kapjuk.

Összefésülő rendezés

\[\begin{split}\begin{align*} &\text{MERGE_SORT}(@A, p, r) \\ &\text{// Input}: A, \text{sorozat} \\ &//\quad\quad\quad\, p, r \in \mathrm{N}, p \leq r \\ &\text{// Output}: A, \text{rendezett sorozat} \\ &\text{IF }p < r\\ &\quad \text{THEN }q \leftarrow \left\lfloor\dfrac{p + r}{2}\right\rfloor\\ &\quad\quad\quad\quad \text{MERGE_SORT}(A, p, q)\\ &\quad\quad\quad\quad \text{MERGE_SORT}(A, q + 1, r)\\ &\quad\quad\quad\quad \text{MERGE}(A, p, q, r)\\ &\text{RETURN}(A) \\ \end{align*}\end{split}\]

\(\rhd\) Egy 10 elemű példán vizsgáljuk meg az algoritmus működését!

\[A = [9, 2, 1, 7, 3, 4, 10, 6, 5, 8]\]

\(\rhd\) Feltételezve, hogy a rekurzívan felbontott részek párhuzamosan is végrehajthatók, ábrázolja az előző számításhoz tartozó Gantt diagramot!

  • Feltételezzük, hogy tetszőleges sok számítási egység rendelkezésünkre áll!

  • Csak az összehasonlítási műveleteket vegyük figyelembe!

\(\rhd\) Határozzuk meg a költség, munka, gyorsítás és hatékonyság értékeket!

\(\rhd\) Mutassuk meg, hogy kisebb gyorsítással adható hatékonyabb megoldás!

Buborék rendezés

Az alapötlete az, hogy

  • elegendő a szomszédos elemeket páronként ellenőrízni, hogy a sorozat rendezett-e, és

  • ha nem megfelelő a pár sorrendje, akkor meg kell cserélni a két elemet.

Az algoritmusnak (szekvenciális esetben is) több változata elképzelhető. A sorozat bejárása történhet

  • az alacsonyabb indexektől a magasabbak felé, vagy

  • a magasabbaktól az alacsonyabbak felé.

\(\rhd\) Nézzük meg az algoritmus működését a következő sorozat rendezésével!

\[A = [8, 6, 3, 1, 5, 4]\]

Párhuzamosítás

Az algoritmus párhuzamosítása problémás.

  • A rendezési mód nehezen fogalmazható meg rekurzív formában.

  • Az elem mozgatása az egész tömbre értendő (tehát a problématér felosztása is körülményes). Ez zárolást tenne szükségessé.

Szinkron rendszert feltételezve indíthatunk párhuzamosan több rendező iterátort.

  • A közöttük lévő különbségnek legalább 1-nek kell lennie.

  • Az utolsónak kell tudni megállapítani, hogy a rendezés során történt-e csere.

  • Egy iterációt követően \(p\)-vel nő a már rendezett elemek száma.

  • Erősen szinkron működést igényel, hogy az iterátorok ne akadjanak össze.

  • A gyakori szinkronizáció költsége nagyobb lehet, mint az összehasonlításé és a cseréjé.

\(\rhd\) Vizsgáljuk meg az előbbi példára a párhuzamos változatot!

\(\rhd\) Rajzoljuk fel a Gantt diagramot!

\(\rhd\) Határozzuk meg a költség, munka, gyorsítás és hatékonyság értékeket!

Shell rendezés

\[\begin{split}\begin{align*} &\text{SHELL_SORT}(@A) \\ &\text{// Input}: A, \text{sorozat} \\ &\text{// Output}: A, \text{a rendezett sorozat}\\ &\text{FOREACH }d \in H\text{ DO}\\ &\quad\text{FOR }j \leftarrow d + 1\text{ TO }n\text{ DO}\\ &\quad\quad x \leftarrow a_j\\ &\quad\quad i \leftarrow j - d\\ &\quad\quad \text{WHILE }i > 0\text{ AND }a_i > x\text{ DO}\\ &\quad\quad\quad a_{i+d} \leftarrow a_i\\ &\quad\quad\quad i \leftarrow i - d\\ &\quad\quad a_{i+d} \leftarrow x\\ &\text{RETURN}(A)\\ \end{align*}\end{split}\]

\(\rhd\) Rendezzük az

\[A = [4, 7, 8, 6, 3, 1, 2, 5]\]

tömböt a \(H = [4, 2, 1]\) növekmények felhasználásával!

Párhuzamosítás

Az azonos távolságokra lévő elemek az egyes iterációkban párhuzamosan rendezhetők.

\(\rhd\) Vizsgáljuk meg az előbbi példára a párhuzamos változatot!

  • Jelezzük külön az összehasonlítás és a csere műveleteket!

  • Feltételezzük, hogy a kettő műveleti ideje azonos!

\(\rhd\) Rajzoljuk fel a Gantt diagramot!

\(\rhd\) Határozzuk meg a költség, munka, gyorsítás és hatékonyság értékeket!

Gyorsrendezés

A felosztáshoz használt algoritmus pszeudó kódja:

\[\begin{split}\begin{align*} &\text{PARTITION}(@A, p, r, x, @q) \\ &\text{// Input}: A, \text{sorozat} \\ &//\quad\quad\quad\, p, r \in \mathrm{N}, p \leq r \\ &//\quad\quad\quad\, x, \text{a felosztáshoz használt elem} \\ &\text{// Output}: A, \text{a felosztott sorozat}\\ &//\quad\quad\quad\, q \in \mathrm{N}, \text{a felosztás határa}, p \leq q \leq r\\ &i \leftarrow p - 1 \\ &j \leftarrow r + 1 \\ &\text{WHILE IGAZ DO} \\ &\quad \text{REPEAT } j \leftarrow j - 1 \\ &\quad \quad \text{UNTIL } a_j \leq x \\ &\quad \text{REPEAT } i \leftarrow i + 1 \\ &\quad \quad \text{UNTIL } a_i \geq x \\ &\quad \text{IF } i < j \\ &\quad \quad \text{THEN } a_i \leftrightarrow a_j \\ &\quad \quad \text{ELSE } q \leftarrow j \\ &\quad \quad \quad \quad \quad \text{RETURN}(A, q) \\ \end{align*}\end{split}\]

A gyorsrendezés algoritmusa:

\[\begin{split}\begin{align*} &\text{QUICKSORT}(@A, p, r) \\ &\text{// Input}: A, \text{sorozat} \\ &//\quad\quad\quad\, p, r \in \mathrm{N}, p \leq r \\ &\text{// Output}: A, \text{a rendezett sorozat}\\ &\text{IF }p < r\text{ THEN}\\ &\quad\text{PARTITION}(A, p, r, a_p, q)\\ &\quad\text{QUICKSORT}(A, p, q)\\ &\quad\text{QUICKSORT}(A, q + 1, r)\\ &\text{RETURN}(A)\\ \end{align*}\end{split}\]

Párhuzamosítás

A felosztást követően a résztömbök függetlenül rendezhetők.

\(\rhd\) Nézzük meg az algoritmus működését a következő sorozat rendezése kapcsán!

\[A = [5, 4, 2, 6, 1, 3]\]

\(\rhd\) Számoljuk meg, hogy mennyi kulcsokra vonatkozó összehasonlítás és csere történt!

\(\rhd\) Rajzoljuk fel a Gantt diagramot!

\(\rhd\) Határozzuk meg a költség, munka, gyorsítás és hatékonyság értékeket!

Leszámláló rendezés

\[\begin{split}\begin{align*} &\text{COUNTING_SORT}(@A, k, @B) \\ &\text{// Input}: A, \text{a rendezendő sorozat} \\ &\text{// Output}: B, \text{a rendezett sorozat}\\ &\text{FOR }i \leftarrow 1 \text{ TO }k\text{ DO}\\ &\quad c_i \leftarrow 0\\ &\text{FOR }j \leftarrow 1\text{ TO }n\text{ DO}\\ &\quad \text{INC}(c_{a_j})\\ &\text{FOR }i \leftarrow 2\text{ TO }k\text{ DO}\\ &\quad c_i \leftarrow c_i + c_{i-1}\\ &\text{FOR }j \leftarrow n\text{ DOWNTO }1\text{ DO}\\ &\quad b_{c_{a_j}} \leftarrow a_j\\ &\quad \text{DEC}(c_{a_j})\\ &\text{RETURN}(B)\\ \end{align*}\end{split}\]

A \(k\) felső korlátként megjelölhető az \(A\) sorozat maximális értéke.

Párhuzamosítás

A 4 lépésnek egymás után kell következnie. Párhuzamosításra azokon belül van lehetőség.

  1. Teljesen párhuzamosítható.

  2. A \(C\) segédtömbhöz való hozzáférés miatt ilyen formában zárolásra van szükség.

  3. Prefix számítási problémaként kezelhető.

  4. Szekvenciálisan hajtandó végre.

\(\rhd\) Egy 8 elemű sorozaton vizsgáljuk meg az algoritmus működését!

Kérdések

  • Adjon példát egy véges (kis elemszámú) halmazon részben rendezésre!

  • Milyen a beszúrásos rendezés időbonyolultsága?

  • Milyen a minimumkiválasztásos rendezés időbonyolultsága?

  • Milyen az összefésülés időbonyolultsága \(n\) és \(m\) méretű bemenetek esetében?

  • Miért előnyös az összefésülő rendezés esetében a \(q\) érték ilyesfajta megválasztási módja? Működne-e az algoritmus tetszőleges \(q \in [p, r]\) esetében?

  • Milyen a buborékrendezés időbonyolultsága?

  • A Shell rendezés esetében mi az elvárás a növekmények sorozatára vonatkozóan?

  • Mi a legrosszabb esete a gyorsrendezésnek (feltéve, hogy mindig az első elemet választjuk pivót elemnek)?

  • Egy 32 elemű tömb rendezése esetében mennyi az optimális rekurzív hívási fa magassága?

Feladatok

Beszúró rendezés

  • Írja fel a beszúró rendezés pszeudó kódját!

  • Mérje le és ábrázolja a kapott eredményeket a beszúró rendezés időbonyolultságára vonatkozóan!

  • Vizsgáljuk meg egy 10 elemű minta rendezése esetében, hogy két beszúró iterátor használatával milyen gyorsítás érhető el! (Feltételezzük, hogy a számítások várakoztatás nélkül párhuzamosan futnak!)

Minimumkiválasztásos rendezés

  • Írja fel a minimumkiválasztásos rendezés pszeudó kódját!

  • Végezzen méréseket az algoritmus időbonyolultságára vonatkozóan!

  • Írjon egy rekurzív felbontásra épülő párhuzamos algoritmust a rendezési feladat megoldására!

  • Hasonlítsa össze azonos bemenetek esetén a szekvenciális és a párhuzamos futási időket!

Összefésülő rendezés

  • Írja fel annak az algoritmusnak a pszeudó kódját, amelyik párhuzamosan fésüli össze a két bemeneti tömb elejét és végét!

  • Írja át a COPY műveletet egy procedúrára úgy, hogy szerepeljenek benne a másoláshoz használt indexek! (Feltételezzük, hogy az eredmény tömb allokálása automatikusan megtörténik.)

  • Írja fel a 2. és 3. WHILE ciklust a COPY eljárás meghívásával!

  • Végezzen becsléseket arra vonatkozóan, hogy milyen gyorsítás lenne elérhető, hogy ha a COPY műveleteket teljesen párhuzamosítva lehetne végrehajtani! (Ehhez készítsen véletlenszerű bemenetekkel futtatásokat, amelyekkel az eredeti összefésülő algoritmust felhasználva meghatározhatja a konkrét összehasonlítások és értékbeállítások számát!)