8.2 Odd-Even-Transposition Sort

Gegeben n Zahlen a₀,a₁,...,a_{n - 1} , gespeichert in einem linearen Prozessorarray
P₀,P₁,P₂,...,P_{n - 1} .

Idee:

Vertausche so lange Nachbarn in falscher Relation, bis Folge sortiert ist.

FOR j := 1 TO n DIV 2 DO
     FOR i := 0, 2, 4, ... DO IN PARALLEL
         Compare_Exchange (a_i,a_{i + 1})
     END
     FOR i := 1, 3, 5, ... DO IN PARALLEL
         Compare_Exchange (a_i,a_{i + 1})
     END
END

                  7-3 6-5 8-1 4-2
                  3 7-5 6-1 8-2 4
                  3-5 7-1 6-2 8-4
                  3 5-1 7-2 6-4 8
                  3-1 5-2 7-4 6-8
                  1 3-2 5-4 7-6 8
                  1-2 3-4 5-6 7-8
                  1 2-3 4-5 6-7 8

Vertauschungen beim Odd-Even-Transposition Sort für 8 Zahlen

Offenbar sind für manche Eingaben mindestens n Iterationen erforderlich (z.B. wenn die größte Zahl vorne steht).

Behauptung:

Nach n Iterationen ist das Array sortiert.

Beweis:

Induktion über n
Sei die Behauptung bis n - 1 bewiesen. Betrachte das Sortieren von n Zahlen. Wie Bild 8.1 zeigt, zerfällt das Schedule längs des Weges, den das Maximum durchläuft, in zwei Teile. Diese beiden Teile lassen sich zu einem Schedule für n - 1 Zahlen zusammenfügen. Nach Induktionsvoraussetzung hat dieses Schedule die Höhe n - 1 . Also verursachen n Zahlen ein Schedule der Höhe n .

$$\bullet$$ Zusammengesetzter neuer Schedule mit n - 1 Zahlen (b)

Die Kosten betragen also O(n ²) , daher liegt kein kostenoptimaler Algorithmus vor.

Es seien nun p < n Prozessoren vorhanden. Jeder Prozessor speichert zu Beginn n/p Zahlen. Zunächst sortiert jeder Prozessor P_i seine Folge sequentiell zu S_i . Dies dauert

In jeder Iteration wird statt compare-exchange (a_i,a_{i + 1}) jetzt merge-and-split (S_i,S_{i + 1}) aufgerufen. Diese Prozedur tauscht zwei sortierte Listen aus, mischt sie und entfernt dann den jeweils kleineren bzw. größeren Teil. Dauer = O(n/p) .

Vor und nach merge-and-split

Bei p Iterationen entsteht also als Gesamtzeit O(${\frac{n}{p}}$ · log ${\frac{n}{p}}$) + p · O(${\frac{n}{p}}$) und bei p Prozessoren als Kosten O(n · log ${\frac{n}{p}}$) + O(n · p) .
Für p < log n ist dies O(n · log n) , somit liegt ein kostenoptimaler Algorithmus vor.