Bubble-Sort mit PThreads

[detonation997]

Hallo,

ich muss ein lineares Array per Threading (im Bubble-Sort-Verfahren) sortieren.

Mein Ansatz wäre, dieses lineare Array in möglichst gleichgroße Teile zu unterteilen, diese per Bubble-Sort in jeweils einem Thread zu sortieren (das funktioniert schon) und anschließend zu mergen (so wird der Vorgang im Buch "Introduction to Parallel Computing" genannt und *leider* nicht näher beschrieben).

Weiß jemand, was mit "compare-split" gemeint ist? So wird der Vorgang (Zusammenfügen der sortierten Array-Parts) nämlich auch genannt.

Hat jemand Erfahrung mit diesem Thema?
Wäre für jeden Hinweis dankbar.

Danke im Voraus,
MfG Rainer

[Joghurt]

Ich würde ganz naiv vermuten, dass du jede der Teillisten nacheinander durchgehst und immer das minimum auswählst.

Beispiel:

1: a b d d i m
2: a j l o p q
3: c c d z z

1. Zeichen:
Erstes Element von liste 1 ist a => 'a' merken
ist erstes Element von liste 2 kleiner als aktuelles zeichen?Nein. Dito bei 3
-> a an neue liste anhängen, liste 1 um eins verkürzen

2. Zeichen:
'b' merken. Liste 2 hat a als erstes element : ('a') merken, später einfügen

[Christoph]

Tschuldingung wenn ich dazwischenschreie: nimm NIEMALS Bubble-Sort. Dies ist ein ineffizientes Sortierverfahren, dessen einziger Vorzug sein drolliger Name ist.

ANSI-C biete die Funktion qsort an, aber ich würde das mit C++ und der sort-Methode in der STL machen.

[detonation997]

Ich MUSS leider Bubble Sort in Threads implementieren. So lautet die Aufgabenstellung.

Danke trotzdem für die Ergänzung!!