Vollständige Version anzeigen : Quicksort parallelisieren


5p34k
12.12.2013, 19:37

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:
;;0;xup~in/tn/2013_12/14956230;png (;;;xup~in/dl,14956230/quicksort;png/)

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 :/

Hardware Preisvergleich | Amazon Blitzangebote!

Videos zum Thema
Video Loading...
xlemmingx
13.12.2013, 13:59

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


Murdoc
13.12.2013, 14:03

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 :D


Smokers
15.12.2013, 20:30

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.


Ähnliche Themen zu Quicksort parallelisieren
  • [PHP] Quicksort (Bekomme die Funktion nicht zum laufen
    Hallo zusammen Ich habe im Netz folgende Funktion zum Quicksort gefunden aber irgendwie bekom ich die nicht zum laufen. Aber jetzt erstmal der Code: <?php function quick_sort($array) $left_arr = quick_sort($left_arr); $right_arr = quick_sort($right_arr); return array_merge( [...]

  • [Delphi] quicksort;bubblesort;shellsort
    Ich versuche gerade diese verfahren auszuarbeiten. Echt komische sache. Finde kein einziges Beispiel was ich mal bei delphi ausprobieren könnte, für jedes einzelne verfahren. Könntet ihr mir vielleicht helfen? Hätte vielleicht jemand ein Beispiel für mich? Jede ordentliche Antwort [...]

  • [Java] Quicksort
    Hi Ich hab Quicksort schon programmiert und brauch dieses auch nicht für Schule/Uni. Wie kann ich in Java Quicksort auf eine LinkedList mit Generics aufrufen. Ich wollte dabei aber auf das von Java vorgefertigte Quicksort drauf zu greifen. Wo finde ich diese in der Javadoc? meine LinkedList sieht [...]

  • Quicksort
    Hallo! Kann mir jemand sagen woher Quicksort weiss wann es terminieren muss? [...]



raid-rush.ws | Imprint & Contact pr