Sortiernetz Shellsort

Bei Verwendung von Bubblesort anstelle des daten­abhängigen Insertionsort lässt sich auch Shellsort (siehe Abschnitt 2.6) als Sortiernetz implementieren. Mit der h-Folge 2^p3^q besteht es aus Θ(n·log(n)²) Vergleichern. Das folgende Bild 1 zeigt ein entsprechendes Sortiernetz für n = 8.

Bild 1: Shellsort-Sortiernetz für n = 8

Nachtrag Beweis

Mit Hilfe des 0-1-Prinzips lässt sich in recht anschau­licher Weise die für Shellsort wichtige Tatsache beweisen, dass eine g-sortierte Folge g-sortiert bleibt, wenn sie h-sortiert wird.

Ganz analog zum Begriff der Inversion bilden zwei Folgen­elemente, die bezüglich der h-Sortierung in falscher Reihenfolge stehen, eine h-Inversion.

Sei eine g-sortierte 0-1-Folge gegeben. Schreibt man die Folge zeilenweise in ein zwei­dimensionales Feld mit g Spalten, so sind die Spalten sortiert. Eine h-Inversion ist gekenn­zeichnet durch eine Eins und eine Null im Abstand kh, k ∈ ℕ, d.h. die Eins steht weiter links oder weiter oben als die Null, jedoch nicht in derselben Spalte. In ein und derselben Spalte kann eine Inversion nicht auf­treten, da die Spalten sortiert sind.

Es ergibt sich also eine Situation wie in Bild 2a (hier haben i und j den Abstand kh = 9, somit könnte in diesem Beispiel h = 1, h = 3 oder h = 9 sein).

Bild 2: (a) g-sortierte Folge mit h-Inversion (i, j),   (b) h-Sortierschritte für eine Spalte, (c) Situation nach den h-Sortierschritten

Nun wird folgendes Verfahren angewandt, um die Folge h-sortiert zu machen. Als Zeilen­kommentare sind Zusicherungen angegeben, die jeweils zwischen den Schritten gültig sind.

Methode:

1. // die Folge ist g-sortiert
2. solange die Folge nicht h-sortiert ist wiederhole
1. // die Folge enthält mindestens eine h-Inversion
2. wähle eine beliebige h-Inversion (i, j);
3. // i und j befinden sich in zwei verschiedenen Spalten
4. beseitige alle h-Inversionen zwischen der Spalte von i und der Spalte von j durch entsprechende h-Sortierschritte;
5. // alle Spalten sind sortiert, d.h. die Folge ist weiterhin g-sortiert
6. // die Anzahl der h-Inversionen hat sich verringert
3. // die Folge ist h-sortiert
4. // die Folge ist g,h-sortiert

Indem immer alle h-Inversionen zwischen zwei Spalten beseitigt werden (Bilder 2b und 2c), bleibt die Bedingung "die Folge ist g-sortiert" bei jedem Durchlauf durch die Schleife erfüllt. Die Bedingung bildet somit eine Schleifen­invariante (siehe Abschnitt Korrektheit von While-Schleifen). Die Anzahl der h-Inversionen wird bei jedem Durchlauf verringert. Die Schleife bricht ab, wenn die Anzahl der h-Inversionen 0 erreicht. Dann ist die Folge h-sortiert, zugleich aber auch noch g-sortiert.

Streng genommen haben wir das 0-1-Prinzip nur für Sortiernetze bewiesen. Hier haben wir kein Sortiernetz, sondern ein daten­abhängiges Sortier­verfahren, dadurch dass zunächst eine h-Inversion gesucht wird. Aber man kann eine entsprechende Argumentation wie beim Beweis des 0-1-Prinzips leicht auf diese Situation übertragen.