Sortiernetze

Satz:  (0-1-Prinzip)

Ein Vergleicher­netz, das alle Folgen von Nullen und Einsen sortiert, ist ein Sortiernetz (d.h. es sortiert auch alle Folgen von beliebigen Werten).

Definition:  Seien A und B geordnete Mengen. Eine Abbildung f : A  B heißt monoton, wenn für alle a₁, a₂  A gilt

a₁a₂      f(a₁)f(a₂)

Hilfssatz:  Sei f eine monotone Abbildung. Dann gilt für alle a₁, a₂  A

f(min(a₁, a₂))  =  min(f(a₁), f(a₂))

Beweis:  Sei zunächst  a₁a₂  und somit  f(a₁)f(a₂). Dann gilt

min(a₁, a₂) = a₁   und   min(f(a₁), f(a₂)) = f(a₁)

Somit ist

f(min(a₁, a₂))  =  f(a₁)  =  min(f(a₁), f(a₂))

Ist a₁ > a₂  und somit f(a₁) > f(a₂), dann gilt analog

f(min(a₁, a₂))  =  f(a₂)  =  min(f(a₁), f(a₂))

Definition:  Sei f eine monotone Abbildung. Die Erweiterung von f auf endliche Folgen a = a₀, ..., a_n-1 sei wie folgt definiert:

f(a₀, ..., a_n-1)  =  f(a₀), ..., f(a_n-1) ,   d.h.

f(a)_i  =  f(a_i)

Hilfssatz:  Sei N ein Vergleicher­netz, f eine monotone Abbildung und a = a₀, ..., a_n-1 eine endliche Folge. Dann gilt:

N( f(a) )  =  f( N(a) )

d.h. es ist dasselbe, ob die monotone Abbildung f vor Eingabe von a in das Vergleicher­netz N angewandt wird oder hinterher.

Beweis:  Zunächst gilt für einen einzelnen Vergleicher [i:j] :

[i:j]( f(a) )_i  =  [i:j]( f(a₀), ..., f(a_n-1) )_i  =  min( f(a_i), f(a_j) )

  =  f( min(a_i, a_j) )  =  f( [i:j](a)_i )  =  f( [i:j](a) )_i

Entsprechendes gilt für die Komponente j sowie für alle anderen Komponenten k. Insgesamt gilt damit

[i:j]( f(a) )  =  f( [i:j](a) )

Da ein Vergleicher­netz eine Hinter­einander­ausführung von Vergleichern ist, gilt somit für ein beliebiges Vergleicher­netz N und jede monotone Abbildung f:

N( f(a) )  =  f( N(a) )

Satz:  Sei N ein Vergleicher­netz. Wenn es eine beliebige Folge gibt, die von N nicht sortiert wird, dann gibt es auch eine 0-1-Folge, die von N nicht sortiert wird.

Beweis:  Sei a mit a_i  A eine Folge, die von N nicht sortiert wird. Dies bedeutet: N(a) = b ist unsortiert, d.h. es gibt einen Index k mit b_k > b_k+1.

Definiere eine Abbildung f : A  {0, 1} wie folgt. Für alle c  A sei

f(c)  =

0       falls   c < bk 1     falls   cbk

Offenbar ist f monoton; ferner gilt:

f(b_k) = 1   und   f(b_k+1) = 0

d.h. f(b) = f(N(a)) ist unsortiert. Damit ist aber auch N(f(a)) unsortiert, und dies bedeutet, dass auch die 0-1-Folge f(a) durch das Vergleicher­netz N nicht sortiert wird.

Wir haben damit gezeigt, dass wenn es eine Folge a gibt, die von N nicht sortiert wird, es auch eine 0-1-Folge f(a) gibt, die von N nicht sortiert wird.

Dies ist gleich­bedeutend damit, dass wenn es keine 0-1-Folge gibt, die von N nicht sortiert wird, es auch keine Folge mit beliebigen Werten gibt, die von N nicht sortiert wird.

Dies ist wiederum gleich­bedeutend damit, dass wenn jede 0-1-Folge von N sortiert wird, auch jede Folge von beliebigen Werten von N sortiert wird.