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

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   Datenschutz   ©   Created: 17.04.2002   Updated: 04.06.2018
Valid HTML 4.01 Transitional