Theoretische Informatik

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:

Shellsort, Shell Sort
direkt ins Video springen
Shellsort

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:

Shellsort Beispiel
direkt ins Video springen
Shellsort Beispiel

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.

Shellsort Iteration
direkt ins Video springen
Shellsort – Letzte Iteration

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 O(n^{1.25}) 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 O(n^2).
  • Die Folge von Hibbard 1, 3, 7, 15, 31,…, 2k– 1 hat eine Laufzeit von O(n^{1,5}).
  • Bei der Folge von Pratt 1, 2, 3, 4, 6, 8, 9, 12,…, 2p3q beträgt die Laufzeitkomplexität O(n \cdot log(n)^2).
  • Eine weitere Folge ist von Sedgewick 1, 8, 23, 77, 281, 1073,…,4k+1+3*2k+1 zeichnet sich durch eine Laufzeit von O(n^{4/3}) aus
  • Die Folge von Knuth 1, 4, 13, 40, 121, 364,…,(3k-1)/2 hat wiederum eine Laufzeit von O(n^{1,5}).

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.

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.