Shellsort
Hier findest du eine ausführliche Shellsort Erklärung. Nach der Darstellung der allgemeinen Grundidee des Sortierverfahrens, wird das Prinzip des Shellsorts durch ein ausführliches Beispiel Schritt-für-Schritt erläutert. Darauf aufbauend folt eine Darstellung von möglichen Java-Implementierung als auch einem Python-Quellcode. Danach werden alle wichtigen Faktoren der Laufzeitkomplexität aufgelistet. Zum Schluss wird die Ähnlichkeit zum Combsort kurz erklärt.
Inhaltsübersicht
Shellsort Erklärung
Der Shellsort, den Donald Shell ursprünglich entwickelte, ist Teil von den instabilen Sortieralgorithmen . Der Das Sortierverfahren arbeitet in-place. Der Shellsort weist prinzipiell das Verhalten eines Insertionsort auf, wodurch er eine Art Variante des Insertionsorts darstellt. Innerhalb des Sortieralgorithmus werden immer Elemente verglichen, die einen bestimmten Abstand voneinander haben und dabei nicht direkt benachbart sind. Wie groß die Feldbreite dabei sein muss, kann selbst bestimmt werden, sollte dabei aber möglichst effizient gewählt werden. Wenn ein Element weit bewegt werden muss, werden viele Bewegungen benötigt. Die Grundidee ist dabei, die Liste so umzusortieren, dass man durch das Entnehmen jedes h-Elements eine geordnete Folge erhält. Während der Sortierungen wird der Wert solange reduziert, bis er 1 wird, womit die Lücke zwischen den Elementen schrittweise verringert wird.
Beispiel
Als Beispiel wird die folgende Liste verwendet: 4, 10, 2, 8, 1, 7, 12, 3, 6, 11, 5, 9. Diese Liste soll von klein nach groß geordnet werden. Als Faktor wird in diesem Beispiel der Wert 4 benutzt. Die Teilsequenzen ordnen sich mittels des Insertionssorts. Damit ergibt sich die folgende neue Ordnung der 1. Iteration:
Daraus ergibt sich eine neue Liste 1, 7, 2, 3, 4, 10, 5, 8, 6, 11, 12, 9. Die folgende Iteration arbeitet mit dem Faktor 2:
Der zweite Durchlauf ist damit abgeschlossen und dadurch entsteht eine neue Reihenfolge der Liste: 1, 3, 2, 7, 4, 8, 5, 9, 6, 10, 12, 11. Die Letzte Iteration sortiert mit dem Faktor 1.
Der Sortiervorgang ist abgeschlossen und es wird die neue, geordnete Liste ausgegeben: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.
Implementierung
Aufgebaut auf dem eben verwendeten Beispiel, werden im folgenden zwei mögliche Implementierungen aufgelistet. Dabei wird ein Shellsort Java-Quellcode und eine Python-Implementierung dargestellt.
Java
public class Shellsort{
public static void sort(int[] liste) {
int inner, outer;
int tmp;
int h = 1;
while (h <= liste.length / 4) {
h = h * 4+ 1;
}
while (h > 0) {
for (outer = h; outer < liste.length; outer++) {
tmp = liste[outer];
inner = outer;
while (inner > h – 1 && liste[inner – h] >= tmp) {
liste[inner] = liste[inner – h];
inner -= h;
}
liste[inner] = tmp;
}
h = (h – 1) / 4;
}
}
public static void main(String[] args) {
int [] liste= {4,10,2,8,1,7,12,3,6,11,5,9};
System.out.println(„Eingabe Liste: “ + Arrays.toString(liste));
sort(liste);
System.out.println(„Sortierte Liste: “ + Arrays.toString(liste));
}
}
Python
def shellsort(liste):
h =len(liste)
gap =h//4
whilegap > 0:
for outer in range(gap,h):
tmp =liste[outer]
inner =outer
while j >=gap andliste[inner-gap] >tmp:
liste[inner] =liste[inner-gap]
inner -=gap
liste[inner] =tmp
gap //=4
liste =[ 4, 10, 2, 8, 1, 7, 12, 3, 6, 11, 5, 9]
h =len(liste)
print(„Eingabeliste:“)
forouter inrange(h):
print(liste [outer]),
shellsort(liste)
print(„\nSortierte Liste:“)
forouter inrange(h):
print(liste [outer]),
Shell Sort Komplexität
Warum sollte man den Shell Sort verwenden, wenn man doch gleich den Insertionsort implementieren könnte? Der Grund liegt darin, dass man durch die Aufteilung in Untersequenzen für viel kürzere Strecken beim Sortierten sorgen kann. Beim herkömmlichen Insertionsort kann der Weg zwischen den Elementen beim Austausch ziemlich groß sein, wodurch der Insertionsort in der Praxis zu einem ineffizienten Sortierverfahren werden kann.
Beim Shellsort ist die Laufzeit – also die Komplexität – immer abhängig von der Wahl der Folge für die Spaltenanzahl. Dabei eine optimale Wahl zu treffen ist sehr schwierig. Je größer die Wahl des Abstands zwischen den einzelnen Sequenzen ist, desto größer sind die entsprechenden Verschiebungen. Im Gegensatz dazu sind bei der Wahl von kleinen Abständen die benötigte Anzahl von Durchläufe des Sortierverfahrens deutlich höher.
Im Allgemeinen wurde aber experimentell belegt, dass im Durchschnitt die Komplexität in etwa bei 
liegt.
Die Laufzeitkomplexität lässt sich jedoch durch die Abhängigkeit bezüglich der Folgen unterschiedlich darstellen, dafür werden im Folgenden einige Beispiele dargestellt:
- Die ursprüngliche Folge von Donald Shell 1, 2, 4, 8, 16,…,2k hat eine Komplexität von
. - Die Folge von Hibbard 1, 3, 7, 15, 31,…, 2k– 1 hat eine Laufzeit von
. - Bei der Folge von Pratt 1, 2, 3, 4, 6, 8, 9, 12,…, 2p3q beträgt die Laufzeitkomplexität
. - Eine weitere Folge ist von Sedgewick 1, 8, 23, 77, 281, 1073,…,4k+1+3*2k+1 zeichnet sich durch eine Laufzeit von
aus - Die Folge von Knuth 1, 4, 13, 40, 121, 364,…,(3k-1)/2 hat wiederum eine Laufzeit von .
Variation – Combsort
Der Combsort ist wie eine Variation des Shellsorts. Während der Shellsort auf dem Insertionsort basiert, ist der Combsort als Verbesserung gegenüber des Bubblesorts zu verstehen. Bei diesem Sortierverfahren wird aber entsprechend durch das Verwenden von Lücken zwischen den zu vergleichenden Elementen die Blasensortierung effizienter gestaltet.