Sortiernetze

Satz:  (0-1-Prinzip)

Ein Vergleichernetz, 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 dagegen 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 Vergleichernetz, 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 Vergleichernetz 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 Vergleichernetz eine Hintereinanderausführung von Vergleichern ist, gilt somit für ein beliebiges Vergleichernetz N und jede monotone Abbildung f:

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

Satz:  Sei N ein Vergleichernetz. 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

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 Vergleichernetz 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 gleichbedeutend 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 gleichbedeutend damit, dass wenn jede 0-1-Folge von N sortiert wird, auch jede Folge von beliebigen Werten von N sortiert wird.