Quicksort parallelisieren

Dieses Thema im Forum "Programmierung & Entwicklung" wurde erstellt von 5p34k, 12. Dezember 2013 .

Schlagworte:
  1. 12. Dezember 2013
    Zuletzt von einem Moderator bearbeitet: 14. April 2017
    Moin moin!

    Ich soll den Quicksort algorithmus parallelisieren. Und zwar hab ich das so gedacht, dass ich erstmal ein Pivotelement bestimme und danach den zu sortierenden Array aufteile. Nun gehe ich die einzelnen teilarrays parallel durch und mache den ersten Schritt vom quicksort algorithmus nämlich alle Elemente, die kleinergleich dem Pivotelement sind in eine seperate Liste schreiben und alle die größer sind in eine andere Liste schreiben. Mein Problem ist, dass ich diese Listen ja nun für jeden Teilarray habe, sprich für jeden Prozess. Ich will aber diese Listen nun zwischen den Prozessen tauschen und zwar soll der Prozess, der den Anfang des sortierenden Arrays "sortiert", mit dem prozess, der das ende des zu sortierenden arrays durchgeht die Liste mit den kleineren Elementen bekommet und dafür aber die Liste mit den größeren Elementen abgibt
    Weiß nicht hoffe das ist verständlich, sonst hier:
    Bild

    Nun ist mein Problem: Wir bekomme ich diese Listen durchgetauscht... Das Problem ist ja, das die Prozesse da irgendwie miteinander kommunizieren... :/

    das ganze soll in C mit OpenMP implementiert werden...

    Hoffe ihr wisst da nen Weg und wenn es nicht geht dann vielleicht einen alternativen Lösungsweg :/
     
  2. 13. Dezember 2013
    AW: Quicksort parallelisieren

    Am einfachsten wäre es wohl wenn du die Teillisten global anlegst sodass alle Prozesse darauf zugreifen können. Müsstest dann eben den Zugriff per Mutex synchronisieren. Ob das auch das effizienteste ist weiß ich nicht...
     
  3. 13. Dezember 2013
    AW: Quicksort parallelisieren

    Mit OpenMP musst du dir eigl. nicht mehr über die Zugriffe Gedanken machen.

    Du machst dir zwei Partitionen der Eingabe (mit ner parallelen schleife) und arbeitest diese dann mit sections ab. Wie es im dritten und vierten Ergebnis bei Google gezeigt wird
     
  4. 15. Dezember 2013
    AW: Quicksort parallelisieren

    am besten nimmst du den quicksort yaroslavski oder wie der chinese hiess ;-) der lässt sich glaube ich noch besser paralelisieren wegen der 2 pivot elemente.
     
  5. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.