Sortiernetze

Odd-even Transposition Sort

 English version  aufwärts

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

Bild 1: Sortiernetz Odd-even Transposition Sort für n = 8
Bild 1: Sortiernetz Odd-even Transposition Sort für n = 8

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 = a0, ..., an-1.

1. Fall: Ist an-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 a0, ..., an-2 sortiert. Das Element an-1 befindet sich bereits an der richtigen Position; somit wird auch a sortiert. Folgendes Bild 2 ver­anschaulicht diesen Fall.

Bild 2: Fall 1 Bild 2: Fall 1
Bild 2: Fall 1

2. Fall: Ist an-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
Bild 3: Fall 2

Es verbleibt ein Odd-even-Trans­position-Vergleicher­netz für n-1 Elemente, das nach Induktions­annahme die Folge a0, ..., an-2 sortiert. Es wird von einer Leitung überkreuzt, die an-1 = 0 an die oberste Position bringt; somit wird auch a sortiert. Damit ist die Behauptung für beliebiges n Element natürliche Zahlen 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(vertikaler Abstand) Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  

 

Weiter mit:   [Odd-even Mergesort]   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