8.3 Sortiernetzwerke

Zur Formulierung paralleler Sortieralgorithmen eignen sich Sortiernetzwerke, in denen der Datenfluß mittels Compare-Exchange-Bausteinen gesteuert wird. Die Laufzeit wird bestimmt durch die Anzahl der Baugruppen, die hintereinander durchlaufen werden.

Definition:

Eine Folge a₀,a₁,...,a_{n - 1} heißt bitonisch $\Leftrightarrow$

1.

$\exists$j : a₀ $\leq$ a₁ $\leq$...$\leq$ a_j $\geq$ a_{j + 1} $\geq$ a_{j + 2} $\geq$...$\geq$ a_{n - 1} oder

2.

die Folge erfüllt Eigenschaft 1 nach zyklischem Shift

Beispiel: 3, 7, 12, 14, 13, 8, 5, 1 ist bitonisch 8, 5, 1, 3, 7, 12, 14, 13 ist bitonisch.

Satz:

Sei a₀,a_1,,...,a_{2n - 1} bitonisch. Dann ist auch d_i = min(a_i,a_{i + n}),i = 0,...,n - 1 und e_i = max(a_i,a_{i + n}),i = 0,...,n - 1 bitonisch. Außerdem gilt für 0 $\leq$ i,j $\leq$ n - 1 : d_i $\leq$ e_j .
Beweisidee: siehe Bild 8.2.

Minimum ( $\bullet$ ) und Maximum ( o ) der Paare (a_i,a_{i + n})

Idee des bitonischen Sortierens:

Eine bitonische Folge a₀,a₁,...,a_{2n - 1} sortiert man, indem man die Folgen d_i,i = 0,...,n - 1 und e_i,i = 0,...,n - 1 bildet, diese sortiert und das Ergebnis konkateniert. Eine beliebige Folge a₀,a₁,...,a_{2n - 1} sortiert man, indem man a₀,...,a_{n - 1} aufsteigend sortiert, a_n,...,a_{2n - 1} absteigend sortiert, die Ergebnisse konkateniert und als bitonische Folge sortiert.