Sortiernetze

Korrektheit von Odd-even Transposition Sort

 aufwärts

Außer mithilfe des 0-1-Prinzips lässt sich die Korrektheit von Odd-even-Trans­position Sort auch in folgender Weise zeigen.

Idee

Es wird ein Verfahren angegeben, um das Odd-even-Trans­position-Sortiernetz durch äquivalente Umformungen in ein Bubblesort-Netz zu überführen und umgekehrt. Da Bubblesort ein Sortiernetz ist, folgt dass auch Odd-even Trans­position Sort ein Sortiernetz ist.

Bild 1 zeigt die Sortiernetze Odd-even-Trans­position Sort und Bubblesort für Datenfolgen der Länge n = 6.

Bild 1: Odd-even Transposition Sort (a) und Bubblesort (b) für n = 6
Bild 1: Odd-even Transposition Sort (a) und Bubblesort (b) für n = 6

Grundlagen

Odd-even Trans­position-Sort und Bubblesort sind primitive Vergleicher­netze, d.h. Vergleiche finden nur zwischen benachbarten Daten­elemente statt. In primitiven Vergleicher­netzen notieren wir einen Vergleicher [i-1 : i] nur durch die Zahl i.

Das Vergleicher­netz Odd-even Trans­position Sort aus Bild 1a entspricht somit der Vergleicher­folge 1 3 5 2 4 1 3 5 2 4 1 3 5 2 4. Das Vergleicher­netz Bubblesort aus Bild 1b entspricht der Vergleicher­folge 1 2 3 4 5 1 2 3 4 1 2 3 1 2 1.

Satz:  Zwei Vergleicher i, j  Element {1, ..., n-1} in einem primitiven Vergleicher­netz sind unabhängig, wenn |i – j| > 1 ist.

Beispiels­weise sind die ersten drei Vergleicher 1, 3, und 5 von Odd-even Trans­position Sort jeweils unabhängig voneinander. Eine Menge von paarweise unabhängigen Vergleichern lässt sich in beliebiger Reihenfolge hinter­einanderausführen (oder parallel ausführen), die entsprechenden Vergleicher­netze sind äquivalent, d.h. bewirken dieselbe Abbildung.

In einem primitiven Vergleicher­netz gilt daher für zwei Vergleicher i und j:

i j  kongruent  j i,   falls |i – j| > 1

Durch derartige Ver­tauschungen von Vergleichern allein lässt sich Odd-even Trans­position Sort noch nicht in Bubblesort überführen. Dies ist erst durch zusätzliche Anwendung der sogenannten Artin-Relation möglich, die wie folgt lautet:

i i+1 i  kongruent  i+1 i i+1

Die Relation drückt aus, dass die folgenden Vergleicher­netze äquivalent sind. Tatsächlich ist dies der Fall, denn es handelt sich um Sortiernetze für n = 3.

Bild 2: Äquivalente Vergleichernetze i i+1 i und i+1 i i+1
Bild 2: Äquivalente Vergleichernetze i i+1 i und i+1 i i+1

Umformung

Durch eine Folge von erlaubten Ver­tauschungen von Vergleichern und Anwendungen der Artin-Relation lässt sich Odd-even Trans­position Sort in Bubblesort überführen. Eine mögliche Strategie besteht darin, alle Vorkommen des Vergleichers n-1 durch mehrfache Anwendung der Relation n-1 n-2 n-1  kongruent  n-2 n-1 n-2 auf ein einziges Vorkommen zu reduzieren, alle Vorkommen von n-2 auf zwei Vorkommen zu reduzieren usw. Bild 3 zeigt die erste entsprechende Anwendung der Artin-Relation.

Bild 3: Ersetzen von 5 4 5 durch 4 5 4
Bild 3: Ersetzen von 5 4 5 durch 4 5 4

Folgende Tabelle zeigt die Überführung eines Odd-even-Trans­position-Sortier­netzes für n = 6 in ein Bubblesort-Netz durch Anwendung von Ver­tauschungen von Vergleichern (V) und Anwendungen der Artin-Relation (A).

135241352413524
V132545132413524
A132454132413524
V132451434213524
A132451343213524
V132413545321324
A132413454321324
V132143454321324
A132134354321324
V132134354323124
A132134354232124
V132134352434212
A132134352343212
V132314352343212
A123214352343212
V123452132343212
A123452123243212
V123452123423212
A123451213423212
V123451234123212
A123451234123121
homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 21.2.2004   Updated: 04.06.2016
Valid HTML 4.01 Transitional