Sortiernetze

Verfahren

Das Sortiernetz Odd-even Trans­position Sort [Knu 73] für n Eingabedaten besteht aus n Vergleicher­stufen, in denen jeweils abwechselnd alle Eingabedaten mit ungeradem Index mit ihren darüber liegenden Nachbarn verglichen werden und dann alle Eingabedaten mit geradem Index (Bild 1). Die Anzahl der Vergleicher beträgt n·(n-1)/2 und entspricht damit genau derjenigen von Bubblesort, die Anzahl der Vergleicher­stufen ist jedoch nur etwa halb so groß.

Korrektheit

Es wird gezeigt, dass Odd-even Trans­position Sort jede beliebige Folge von Nullen und Einsen sortiert. Nach dem 0-1-Prinzip wird dann auch jede Folge von beliebigen Elementen sortiert. Der Beweis wird durch vollständige Induktion über die Problemgröße n geführt.

Behauptung: Das Odd-even-Trans­position-Vergleicher­netz für n Elemente sortiert jede 0-1-Folge der Länge n.

Induktions­anfang: n = 1
Das Odd-even-Trans­position-Vergleicher­netz für ein Element besteht aus lediglich einer durch­gezogenen waagerechten Linie mit 0 Vergleichern. Da jede 0-1-Folge der Länge 1 bereits sortiert ist, ist die Behauptung für n = 1 bewiesen.

Induktions­annahme: Die Behauptung sei für n-1 erfüllt.

Induktions­schluss:
Gegeben sei ein Odd-even-Trans­position-Vergleicher­netz für n > 1 Elemente, ferner eine beliebige 0-1-Folge a = a₀, ..., a_n-1.

1. Fall: Ist a_n-1 = 1, so bewirken die unteren Vergleicher [n-2:n-1] nichts und können entfallen. Es verbleibt ein Odd-even-Trans­position-Vergleicher­netz für n-1 Elemente (plus eine überflüssige Vergleicher­stufe), das nach Induktions­annahme die Folge a₀, ..., a_n-2 sortiert. Das Element a_n-1 befindet sich bereits an der richtigen Position; somit wird auch a sortiert. Folgendes Bild 2 ver­anschaulicht diesen Fall.

Bild 2: Fall 1

2. Fall: Ist a_n-1 = 0, so führen alle Vergleicher, auf die diese Null trifft, eine Vertauschung durch (auch wenn ein Vergleicher in Wirklichkeit keine Vertauschung durchführt, weil das andere zu ver­gleichende Element auch eine Null ist, ist das Ergebnis dasselbe). Die entsprechenden Vergleicher können somit durch sich über­kreuzende Linien ersetzt werden (Bild 3).

Bild 3: Fall 2

Es verbleibt ein Odd-even-Trans­position-Vergleicher­netz für n-1 Elemente, das nach Induktions­annahme die Folge a₀, ..., a_n-2 sortiert. Es wird von einer Leitung überkreuzt, die a_n-1 = 0 an die oberste Position bringt; somit wird auch a sortiert. Damit ist die Behauptung für beliebiges n ∈ ℕ bewiesen.

Es ist auch möglich, Odd-even Trans­position Sort durch Umformung in Bubblesort zu beweisen.

Literatur

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

[Lan 12]   H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Das Verfahren Odd-even-Transposition Sort sowie andere Sortiernetze wie Bitonic Sort oder Odd-even Mergesort finden Sie auch in meinem Buch über Algorithmen.
Weitere Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]