11.01.2020Shellsort ist nach seinem Erfinder benannt, Donald Shell. Wenn Mergesort durch wiederholtes zusammenführen funktioniert, und Quicksort durch wiederholtes partitionieren eines Arrays, dann funktioniert Shellsort durch wiederholtes ausführen von Insertionsort mit verschiedenen Schrittweiten im Array. Shellsort arbeitet in-situ und ist stabil, genau wie Insertionsort. Aber auf großen Arrays bietet er oft schnellere Geschwindigkeit als Insertionsort.
Das obige Panel zeigt wie Arrays auf dieser Seite dargestellt werden, wobei die Säulen die Größe der Zahlen anzeigen.
Im obigen Array, beginnend mit dem ersten Eintrag, wird aus jedem vierten Eintrag ein Unterarray gebildet, welches in blau markiert wird. Dieses Unterarray wird mit Insertionsort sortiert, so dass am Ende die grün schattierten Kästchen eine sortierte Sequenz enthalten. Dies geht relativ schnell durch, da es nur wenige solche Einträge in diesem kleinen Array gibt. Dies ist der Grundschritt von Shellsort.
Die im vorherigen Panel beschriebenen Prozedur kann für alle 4 möglichen Startpunkte wiederholt werden, bis alle Elemente im Array an einer Sortierung teilgenommen haben. Man nennt das Array dann 4-sortiert, weil 4 die Schrittweite der Sortiervorgänge ist. Im Allgemeinen, enthält eine k-sortiertes Array k Unterarrays, die alle in Bezug auf ihre Nachbarn in einer Sequenz der Schrittweite k sortiert sind.
Die ganze Shellsort Prozedur läuft so ab: man beginne mit einem ausreichend großem Wert k, und sortiert das Array um eine k-Sortierung zu erhalten. Dann wird k entsprechend verringert und das ganze wird wiederholt. Zum Schluss hat k den Wert 1, und der Sortiervorgang wird auf ein Insertionsort reduziert. Zu diesem Zeitpunkt ist das Array beinahe vollständig sortiert und der Insertionsort Durchgang läuft relativ schnell durch, und hinterläßt ein vollständig sortiertes Array.
Der undurchsichtigste Teil an Shellsort ist die Auswahl der Werte für k. Hier nutzen wir eine Standardschema bei dem der nächsthöhere Wert von k durch die Formel k = 3k + 1 gegeben wird. Beginnend mit 1 berechnet man also solche Werte bis die Länge des Array überschritten würde, dann beginnt die Sortierung mit dem größten k Wert. Nach jeder k-Sortierung wird der nächstkleinere Wert genommen, in diesem Fall aus der Sequenz 13, 4, 1.
Dieses Panel zeigt ein monoton fallendes Array als Eingabe. Für manche Algorithmen ist dies schwerer zu sortieren als rein zufällige Eingaben. Wie man aber sehen kann, verarbeitet Shellsort diese Eingabe recht gut. Die Laufzeit ist nicht viel höher als bei den zufälligen Werten die wir bisher betrachtet haben.
Dieses Panel zeigt wie Shellsort ein größeres Array mit 101 Zahlen sortiert, mit einer höheren Animationsgeschwindigkeit. Mit einem Array dieser größe wird der initiale k Wert auf 40 gesetzt.
So weit scheint Shellsort vielleicht nicht allzu schnell zu sein. Es hat aber den Geschwindigkeitsvorteil gegenüber vielen anderen einfachen Algorithmen, wie zum Beispiel Insertionsort. Zum Vergleich zeigt das Panel oben die Sortierung eines Arrays von der selben Größe wie das auf dem vorigen Panel, aber diesmal mit Insertionsort. Auf der erste Häfte des Arrays scheint Insertionsort zu gewinnen, aber auf dem ganzen Array ist Shellsort schneller. Je größer das Array ist, desto signifikanter wird dieser Unterschied sein.