Sortiernetze Odd-even Transposition Sort

Verfahren

Das Sortiernetz Odd-even Transposition 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.

 

Korrektheit

Es wird gezeigt, dass Odd-even Transposition 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-Transposition-Vergleicher­netz für n Elemente sortiert jede 0-1-Folge der Länge n.

Induktionsanfang: n = 1
Das Odd-even-Transposition-Vergleicher­netz für ein Element besteht aus lediglich einer durchgezogenen 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.

Induktionsschluss:
Gegeben sei ein Odd-even-Transposition-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-Transposition-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 vergleichende Element auch eine Null ist, ist das Ergebnis dasselbe). Die entsprechenden Vergleicher können somit durch sich überkreuzende Linien ersetzt werden (Bild 3).

Bild 3:  Fall 2

Es verbleibt ein Odd-even-Transposition-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 Transposition 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 06]	H.W. Lang: Algorithmen in Java. 2. Auflage, Oldenbourg (2006) Das Verfahren Odd-even-Transposition Sort finden Sie auch in meinem Buch über Algorithmen. Weitere Themen des Buches: Sortieren, Textsuche, Parsen und Übersetzen, Graphen­algorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortier­algorithmen. [Weitere Informationen]   [Bestellen]

 

 

Weiter mit:   [Odd-even Mergesort]   oder

 

H.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 21.10.2001   Updated: 18.05.2010