Sortiernetze

0-1-Prinzip

 English version  aufwärts

Außer­ordentlich hilfreich für den Beweis von Sortier­netzen ist folgender Satz, der als 0-1-Prinzip bezeichnet wird [Knu 73]. Er besagt, dass die Tatsache, ob ein Vergleicher­netz ein Sortiernetz ist oder nicht, nur von seiner Struktur abhängt und nicht vom Eingabe­daten­bereich A.

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).

Der Beweis des 0-1-Prinzips ist eigentlich recht einfach. Um ihn technisch sauber zu führen, sind jedoch zunächst einige Definitionen und zwei Hilfssätze erforderlich.

Hilfssätze

Definition:  Seien A und B geordnete Mengen. Eine Abbildung f : A Pfeil nach rechts B heißt monoton, wenn für alle a1, a2 Element A gilt

a1kleiner gleicha2   folgt   f(a1)kleiner gleichf(a2)

Hilfssatz:  Sei f eine monotone Abbildung. Dann gilt für alle a1, a2 Element A

f(min(a1, a2))  =  min(f(a1), f(a2))

Beweis:  Sei zunächst  a1kleiner gleicha2  und somit  f(a1)kleiner gleichf(a2). Dann gilt

min(a1, a2) = a1   und   min(f(a1), f(a2)) = f(a1)

Somit ist

f(min(a1, a2))  =  f(a1)  =  min(f(a1), f(a2))

 

Ist dagegen a2kleiner gleicha1  und somit f(a2)kleiner gleichf(a1), dann gilt analog

f(min(a1, a2))  =  f(a2)  =  min(f(a1), f(a2))

Eine entsprechende Aussage gilt für die max-Funktion.

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

f(a0, ..., an-1)  =  f(a0), ..., f(an-1) ,   d.h.

f(a)i  =  f(ai)

Hilfssatz:  Sei N ein Vergleicher­netz, f eine monotone Abbildung und a = a0, ..., an-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(a0), ..., f(an-1) )i  =  min( f(ai), f(aj) )

  =  f( min(ai, aj) )  =  f( [i:j](a)i )  =  f( [i:j](a) )i

Ent­sprechendes 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­einanderausführung von Vergleichern ist, gilt somit für ein beliebiges Vergleicher­netz N und jede monotone Abbildung f:

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

Beweis des 0-1-Prinzips

Wir formulieren das 0-1-Prinzip umgekehrt:

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 ai Element A eine Folge, die von N nicht sortiert wird. Dies bedeutet: N(a) = b ist unsortiert, d.h. es gibt einen Index k mit bk > bk+1.

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

 f(c)  =   geschweifte Klammer
0      falls   c < bk
1    falls   cgrößer gleichbk

Offenbar ist f monoton; ferner gilt:

f(bk) = 1   und   f(bk+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.

Literatur

[Knu 73]D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)

 

Weiter mit:   [Bubblesort]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 21.10.2001   Updated: 04.06.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik