ShellSort ist ein von Donald L. Shell entwickelter Sortieralgorihtmus aus dem Jahre 1959. Er basiert auf dem Prinzip von InsertionSort.
Idee
InsertionSort ist sehr effizient bei genügend vorsortierten Daten, aber langsam, weil Elemente pro Iterationsschritt nur maximal um eine Position bewegt werden. ShellSort verbessert nun InsertionSort indem Elemente, die eine bestimmte Entfernung voneinander entfernt sind (gap size), vergleicht und sie notfalls vertauscht. Die gap size wird nach jeder Iteration verringert, sodass der nächste Iterationsschritt auf leicht vorsortierten Daten basiert.
Um dies bildlich zu veranschaulichen, behilft man sich einer Matrixdarstellung mit k Spalten, wobei k die gap size repräsentiert. Jede Spalte wird dann separat mit dem InsertionSort sortiert. Dies geschieht vergleichsweise schnell auf diesen kleinen Datensätzen. Im nächsten Schritt wird die gap size verringert ung der Algortihmus wiederholt. Im letzten Schritt liegt eine einspaltrige Matrix vor, worauf ein InsertionSort eine sortierte Folge garantiert und zudem schnell ablaufen sollte, da sie nun genügend vorsortiert sein müsste.
Applet
© Miao Wang 2006 (Bug-Meldungen bitte an Webmaster@Wanginator.de richten)
Das Applet (benötigt Java) visualisiert einen ShellSort auf maximal 16 Elemente. Der Algorithmus läuft wie oben beschrieben ab, wobei nun kedoch die Zeilenanzahl (anstatt die Spaltenanzahl) gap size gewählt wurde, damit das Applet gut auf die Seite passt. Mit Insert lassen sich Werte zur Folge hinzufügen, mit Random Fill erhält man eine zufällige volle Folge generiert und mit Clear löscht man die aktuelle Folge. Mit einem Klick auf Sort wird stets ein Schritt des Verfahrens visualisiert.
Quellcode (Java)
Varianten
Combsort ist ein ähnliches Sortierverfahren, welches statt dem InsertionSort eine Iteration des BubbleSort benutzt um die Spalten vorzusortieren.
Analyse
Die Laufzeit von ShellSort zu analysieren ist sehr schwer und gehen von O(n log2 n) bis O(n1.5) je nach Implementation. Sie hängt vor allem von der Wahl der gap sizes ab. Die Folge 1, 3, 7, 15, 31, 63, ..., 2k-1 führt zu einer Laufzeit von O(n1.5), die Folge 1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2p3q jedoch zu einer Laufzeit von O(n log2 n). Es kann gezeigt werden, dass die durchschnittliche Laufzeit bei etwa O(n1.25) liegt, aber ein Beweis für ein O(n log n) WorstCase wurde noch nicht gefunden.
Further References
Weiterführende Links und Literatur
