10. tétel - Párhuzamos rendezés

Milyen módon párhuzamosítható a buborékrendezés? Ismertesse a páros-páratlan felbontás elvi alapjait! Mutassa be az oszd meg és uralkodj elvű megoldásokat párhuzamos rendezésre!

Buborékrendezés párhuzamosítása

Szekvenciális buborékrendezés

  • működése két egymásba ágyazott cikluson alapul, amelyek hatásaként páronként összehasonlításra kerülnek az egymás melletti elemek, és szükség esetén csere történik
  • N-1 darab fázis van
    • az első fázisban N-1 összehasonlítás, aztán mindegyik fázisban eggyel kevesebb
    • az első fázisban a tömb utolsó eleme kerül a helyére, a következőben az utolsó előtti, és így tovább
  • Az összehasonlítások száma összesen \( \frac{N(N−1)}{2} \), a futásidő \(O(N^2)\)

Szekvenciális buborékrendezés

Párhuzamosítás

Futószalag elvű

  • Az első fázis elindulásakor az első két elem kerül összehasonlításra és esetleg cserére, ezt követően a 2. és 3. elemek. Amikor a 3. és 4. elemekre kerül a sor, akkor a második fázis indítható az első és második elemek feldolgozásával, hisz az első fázis a továbbiakban nem érinti ezeket, és így tovább.
  • Működőképes, de
    • szinkronizálni kell a feldolgozást, mert el kell kerülni a versenyhelyzetet
      • a később indult fázis ne tudjon a következő elempárra lépni, amíg a korábban indult azokat még nem dolgozta fel
    • nem hatékony: a műveletvégzők száma nem azonos végig
      • kezdetben 1
      • legfeljebb \(\frac{1}{2}\)-re növekszik
      • majd az utolsó fázisoknál ismét lecsökken

Párhuzamos buborékrendezés

Páros-páratlan felbontás elvi alapjai

  • hatékonyabb, mint a futószalagos megoldás
  • összesen \(N\) darab konkurens lépés történik, melyek között megkülönböztetünk páros és páratlan fázisokat
    • páros fázis: a páros sorszámú elemek kerülnek összehasonlításra (és cserére) a jobb oldali szomszédjukkal;
    • páratlan fázis: a páratlan sorszámú elemek kerülnek összehasonlításra (és cserére) a jobb oldali szomszédjukkal
  • így összesen \(\Bigl\lceil \frac{N}{2} \Bigr\rceil\) db, egy páros és egy páratlan fázisból álló iteráció kell csak a rendezéshez
    • ezáltal a szükséges műveletvégzők száma \(\Bigl\lfloor \frac{N}{2} \Bigr\rfloor\)
  • előny: műveletvégzők kihasználtsága jó
  • hátrány: overheadet okoz az elemek konkurens elérésének biztosítása

Buborékrendezés párhuzamosan, páros-páratlan felbontással

Oszd meg és uralkodj elvű megoldások párhuzamos rendezésre

Összefésülő rendezés

  • a tömb előbb megfelezésre kerül, majd az előállított résztömb további felezésével egyre kisebb részfeladatokra bomlik
  • amikor a résztömbök már csak 1 elemet tartalmaznak, akkor a szomszédos blokkok összefésüléssel egyesülnek
  • A szekvenciális futásidő \(O(N \log N)\) függvényében adható meg

Párhuzamosítás

  • Két szakasz:
    • felbontás: \(\lceil \log N \rceil\) lépés
    • egyesítés: \(\lceil \log N \rceil\) lépés
  • Fork/Join mintán alapul
  • szintenként lefelé haladva különböző, egyre nagyobb elemszámú tömbök összefésülése szükséges
    • a műveletek száma, időigénye különböző

Összefésülő rendezés

Gyorsrendezés

  • egy támpontnak (pivot) nevezett elem szerint kerül felbontásra a tömb
  • E támpont elem elé mozgatjuk a kisebb, mögé pedig a nagyobb elemeket
    • a támpont elem a végleges helyére kerül
    • a két résztömb pedig függetlenül rendezhető
  • Ha a résztömb nem egységnyi méretű, akkor ismét szétválogatás, majd felbontás következik.
  • a támpont választás befolyásolja a futásidőt
    • átlagban \(O(N \log N)\)
    • rossz esetben \(O(N^2)\)
  • szintén Fork/Join minta

Gyorsrendezés

(A támpont elem ebben a példában mindig a tömb vagy résztömb első eleme.)