Benutzer:JensKohl/Inkubator/Parallel Sorting by Regular Sampling

Parallel Sorting by Regular Sampling (zu deutsch etwa: Paralleles Sortieren mit regulären Proben) ist ein kostenoptimaler, paralleler Algorithmus. Dieser Algorithmus vermeidet den redundanten Austausch von Pivotelementen, wie er etwa bei beispielsweise Hyperquicksort vorkommt. Der Algorithmus gliedert sich in vier Phasen und weißt eine parallele Zeitkomplexität von $\textstyle {\mathcal {O}}({\frac {n}{p}}\log _{2}(p)+p^{2}\log _{2}(p))$ auf. Falls $\textstyle n>=p^{2}$ ist, so dominiert der vordere Term, so dass der Aufwand zu $\textstyle {\mathcal {O}}({\frac {n\cdot \log _{2}(n)}{p}})$ optimal, mit $\textstyle p$ Prozessoren wird.

Beispiel

• Phasen einzeln beschreiben
• In Tabelle pro Phase den Zustand anzeigen.

[Kategorie:Parallelverarbeitung|Parallele Programmierung]