6. Előadás - Rendező algoritmusok

Rendező algoritmusok

A $ρ$ (részben) rendezési reláció tulajdonságai:

reflexív: $a ρ a, \forall a \in A$
antiszimmetrikus: $a ρ b$ és $b ρ a$ esetén $a = b$
tranzitív: $a ρ b$ és $b ρ c$ esetén $a ρ 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.)

$⊳$ 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.

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

$⊳$ 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.

$⊳$ 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) = \sum_{i = 1}^{n} \log_{2} (i) .

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

$⊳$ Egy 5 elemű példán nézzük meg az algoritmus működését!

$⊳$ 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{aligned} \begin{aligned} MERGE_ARRAYS (@ A, @ B, @ C) \\ // Input : A \in R^{n} \\ / / B \in R^{m} \\ // Output : C \in R^{n + m} \\ i \leftarrow 1, j \leftarrow 1, k \leftarrow 1 \\ WHILE i \leq n AND j \leq m DO \\ IF a_{i} \leq b_{j} \\ THEN c_{k} \leftarrow a_{i} \\ i \leftarrow i + 1 \\ ELSE c_{k} \leftarrow b_{j} \\ j \leftarrow j + 1 \\ k \leftarrow k + 1 \\ WHILE i \leq n DO \\ c_{k} \leftarrow a_{i} \\ i \leftarrow i + 1 \\ k \leftarrow k + 1 \\ WHILE j \leq m DO \\ c_{k} \leftarrow b_{j} \\ j \leftarrow j + 1 \\ k \leftarrow k + 1 \\ RETURN (C) \end{aligned} \end{aligned}

Egy bemeneti tömbös változat

\begin{aligned} \begin{aligned} MERGE (@ A, p, q, r) \\ // Input : A, sorozat \\ / / p, q, r \in N, p \leq q \leq r \\ // Output : A, rendezett sorozat \\ X \leftarrow COPY (A) \\ i \leftarrow 1, j \leftarrow q + 1, k \leftarrow 1 \\ WHILE i \leq q AND j \leq r DO \\ IF x_{i} \leq x_{j} \\ THEN a_{k} \leftarrow x_{i} \\ i \leftarrow i + 1 \\ ELSE a_{k} \leftarrow x_{j} \\ j \leftarrow j + 1 \\ k \leftarrow k + 1 \\ WHILE i \leq q DO \\ a_{k} \leftarrow x_{i} \\ i \leftarrow i + 1 \\ k \leftarrow k + 1 \\ WHILE j \leq r DO \\ a_{k} \leftarrow x_{j} \\ j \leftarrow j + 1 \\ k \leftarrow k + 1 \\ RETURN (A) \end{aligned} \end{aligned}

$⊳$ Vizsgáljuk meg az algoritmus működését egy 12 elemű példán!

$⊳$ 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{aligned} \begin{aligned} A & = {a_{1}, a_{2}, a_{3}, \dots} \\ B & = {b_{1}, b_{2}, b_{3}, \dots} \end{aligned} \end{aligned}

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

\begin{aligned} \begin{aligned} A_{1} & = {a_{1}, a_{3}, a_{5}, \dots} \\ A_{2} & = {a_{2}, a_{4}, a_{6}, \dots} \\ B_{1} & = {b_{1}, b_{3}, b_{5}, \dots} \\ B_{2} & = {b_{2}, b_{4}, b_{6}, \dots} \end{aligned} \end{aligned}

Fésüljük össze ezeket az $U$ és $V$ sorozatokba:

\begin{aligned} \begin{aligned} A_{1}, B_{2} \to U \\ A_{2}, B_{1} \to V \end{aligned} \end{aligned}

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

Összefésülő rendezés

\begin{aligned} \begin{aligned} MERGE_SORT (@ A, p, r) \\ // Input : A, sorozat \\ / / p, r \in N, p \leq r \\ // Output : A, rendezett sorozat \\ IF p < r \\ THEN q \leftarrow ⌊ \frac{p + r}{2} ⌋ \\ MERGE_SORT (A, p, q) \\ MERGE_SORT (A, q + 1, r) \\ MERGE (A, p, q, r) \\ RETURN (A) \end{aligned} \end{aligned}

$⊳$ 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]

$⊳$ 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!

$⊳$ Határozzuk meg a költség, munka, gyorsítás és hatékonyság értékeket!

$⊳$ 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é.

$⊳$ 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é.

$⊳$ Vizsgáljuk meg az előbbi példára a párhuzamos változatot!

$⊳$ Rajzoljuk fel a Gantt diagramot!

$⊳$ Határozzuk meg a költség, munka, gyorsítás és hatékonyság értékeket!

Shell rendezés

\begin{aligned} \begin{aligned} SHELL_SORT (@ A) \\ // Input : A, sorozat \\ // Output : A, a rendezett sorozat \\ FOREACH d \in H DO \\ FOR j \leftarrow d + 1 TO n DO \\ x \leftarrow a_{j} \\ i \leftarrow j - d \\ WHILE i > 0 AND a_{i} > x DO \\ a_{i + d} \leftarrow a_{i} \\ i \leftarrow i - d \\ a_{i + d} \leftarrow x \\ RETURN (A) \end{aligned} \end{aligned}

$⊳$ 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.

$⊳$ 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!

$⊳$ Rajzoljuk fel a Gantt diagramot!

$⊳$ 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{aligned} \begin{aligned} PARTITION (@ A, p, r, x, @ q) \\ // Input : A, sorozat \\ / / p, r \in N, p \leq r \\ / / x, a felosztáshoz használt elem \\ // Output : A, a felosztott sorozat \\ / / q \in N, a felosztás határa, p \leq q \leq r \\ i \leftarrow p - 1 \\ j \leftarrow r + 1 \\ WHILE IGAZ DO \\ REPEAT j \leftarrow j - 1 \\ UNTIL a_{j} \leq x \\ REPEAT i \leftarrow i + 1 \\ UNTIL a_{i} \geq x \\ IF i < j \\ THEN a_{i} \leftrightarrow a_{j} \\ ELSE q \leftarrow j \\ RETURN (A, q) \end{aligned} \end{aligned}

A gyorsrendezés algoritmusa:

\begin{aligned} \begin{aligned} QUICKSORT (@ A, p, r) \\ // Input : A, sorozat \\ / / p, r \in N, p \leq r \\ // Output : A, a rendezett sorozat \\ IF p < r THEN \\ PARTITION (A, p, r, a_{p}, q) \\ QUICKSORT (A, p, q) \\ QUICKSORT (A, q + 1, r) \\ RETURN (A) \end{aligned} \end{aligned}

Párhuzamosítás

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

$⊳$ 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]

$⊳$ Számoljuk meg, hogy mennyi kulcsokra vonatkozó összehasonlítás és csere történt!

$⊳$ Rajzoljuk fel a Gantt diagramot!

$⊳$ Határozzuk meg a költség, munka, gyorsítás és hatékonyság értékeket!

Leszámláló rendezés

\begin{aligned} \begin{aligned} COUNTING_SORT (@ A, k, @ B) \\ // Input : A, a rendezendő sorozat \\ // Output : B, a rendezett sorozat \\ FOR i \leftarrow 1 TO k DO \\ c_{i} \leftarrow 0 \\ FOR j \leftarrow 1 TO n DO \\ INC (c_{a_{j}}) \\ FOR i \leftarrow 2 TO k DO \\ c_{i} \leftarrow c_{i} + c_{i - 1} \\ FOR j \leftarrow n DOWNTO 1 DO \\ b_{c_{a_{j}}} \leftarrow a_{j} \\ DEC (c_{a_{j}}) \\ RETURN (B) \end{aligned} \end{aligned}

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.

Teljesen párhuzamosítható.
A $C$ segédtömbhöz való hozzáférés miatt ilyen formában zárolásra van szükség.
Prefix számítási problémaként kezelhető.
Szekvenciálisan hajtandó végre.

$⊳$ 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!)