Shellsort

 aufwärts

Sortiernetz Shellsort

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

Bild 1: Shellsort-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 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 zweidimensionales 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 2a (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 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 Zeilenkommentare sind Zusicherungen angegeben, die jeweils zwischen den Schritten gültig sind.

 

h-Sortieren einer g-sortierten Folge
Methode:
  1. // die Folge ist g-sortiert

    solange die Folge nicht h-sortiert ist wiederhole

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

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

      // i und j befinden sich in zwei verschiedenen Spalten

      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 2b und 2c), bleibt die Bedingung "die Folge ist g-sortiert" bei jedem Durchlauf durch die Schleife erfüllt. Die Bedingung bildet somit eine Schleifeninvariante (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 datenabhängiges Sortierverfahren, 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   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 17.04.2002   Updated: 29.05.2016
Valid HTML 4.01 Transitional