Lokale Demo
Wenn ein fester Vergleichsplan auf xi scheitert, dann auch auf xi*
Gezeigt wird die Beweisidee von Knuths
0-1-Sortierlemma: ein fester, absichtlich fehlerhafter
Vergleichsplan verarbeitet erst eine Folge
x1, ..., xn und dann die daraus
gebildete Bitfolge x1*, ..., xn*.
Fester Vergleichsplan
Eingabe x
Falsche Ausgabe
Richtig sortiert
Fester fehlerhafter Vergleichsplan
Der Vergleichsplan steht von vornherein fest und hängt nicht von den Daten ab. Genau das ist die Voraussetzung im Lemma.
Gleicher Plan auf x und auf x*
Erste falsche Stelle
Spätere Position von xπ(k)
Schwelle
Bitprojektion
Lauf auf xi
Die Spalten k und r sind dauerhaft
markiert. Am Ende sieht man: an Stelle k steht ein
zu großer Wert, und xπ(k) ist erst
später bei r.
Lauf auf xi*
Es wird derselbe Vergleichsplan ausgeführt. Am Ende ist
sichtbar: xσ(k)* = 1
und xσ(r)* = 0.
Richtig sortierte Reihenfolge
Zum Vergleich: so müsste die Ausgabe aussehen.