Shellsort

Nachtrag Beweis

 aufwärts

g-Sortierung bleibt bei h-Sortierung erhalten

Mit Hilfe des 0-1-Prinzips lässt sich in recht anschaulicher 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 Folgenelemente, die bezüglich der h-Sortierung in falscher Reihenfolge stehen, eine h-Inversion.

Definition:  Sei a = a0, ..., an-1 eine Folge von Daten. Ein Zahlenpaar (i, j) mit i, j Element {0, ..., n-1} heißt h-Inversion, wenn i+kh = j und ai > aj ist (k Element natürliche Zahlen).

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 gekennzeichnet durch eine Eins und eine Null im Abstand kh, k Element natürliche Zahlen, 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 auftreten, da die Spalten sortiert sind.

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

g-sortierte Folge und Anwendung von h-Sortierschritten
Bild 1:  (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.

 

h-Sortieren einer g-sortierten Folge
Methode:

  1. // die Folge ist g-sortiert

  2. solange die Folge nicht h-sortiert ist

    1. // die Folge enthält mindestens eine h-Inversion

    2. wähle eine beliebige h-Inversion (i, j);

      // i und j befinden sich in zwei verschiedenen Spalten

    3. beseitige alle h-Inversionen zwischen der Spalte von i und der Spalte von j durch entsprechende h-Sortierschritte;

      // alle Spalten sind sortiert, d.h. die Folge ist weiterhin g-sortiert

      // die Anzahl der h-Inversionen hat sich verringert

    // die Folge ist h-sortiert

    // die Folge ist g,h-sortiert

 

Indem immer alle h-Inversionen zwischen zwei Spalten beseitigt werden (Bilder 1b und 1c), bleibt die Bedingung "die Folge ist g-sortiert" bei jedem Durchlauf durch die Schleife erfüllt. Die Bedingung bildet somit eine sogenannte Schleifen­invariante. 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.

 

 

Weiter mit:   up

 

homeH.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 17.04.2002   Updated: 18.05.2010
 Valid HTML 4.01 Transitional