Eine Einführung in den Shell-Sort-Algorithmus
Shell-Sort ist eine Sortiertechnik, die eine gegebene Liste in Unterlisten aufteilt und diese dann mit Insertion-Sort sortiert. Der Algorithmus verwendet eine Lücke n , die Elemente auswählt, die n Lücken voneinander entfernt sind, um die Unterlisten zu umfassen.
Die Unterlisten werden dann mit Insertion-Sort sortiert und anschließend kombiniert. Die kombinierte Liste ist nicht vollständig sortiert, bietet dem Algorithmus jedoch den Vorteil, dass die Elemente näher an ihrer endgültigen Position liegen.
Die Einfügungssortierung wird wieder verwendet, um die Liste endgültig zu sortieren.
Ein genauerer Blick auf Shell Sort
Die obige Beschreibung hat vielleicht nicht viel Sinn gemacht, aber ein Beispiel sollte helfen. Angenommen, Sie haben die Liste: [39, 6, 2, 51, 30, 42, 7, 4, 16] und einen Lückenwert von drei.
Die erste Unterliste würde Elemente enthalten: 39, 51, 7
Die zweite Unterliste: 6, 30, 4
Die dritte & letzte Unterliste: 2, 42, 16
Nach der Einfügungssortierung würde jede der Unterlisten wie folgt sortiert:
Die erste: 7, 39, 51
Die zweite: 4, 6, 30
Der dritte: 2, 16, 42
Die sortierte Unterliste wird nun auf eine bestimmte Weise zusammengefasst. Jedes Unterlistenelement wird in den Index eingefügt, aus dem der ursprüngliche unsortierte Unterlistenwert gesammelt wurde.
Sie erhalten daher die folgende Sequenz:
[7, 4, 2, 39, 6, 16, 51, 30, 42]
Beachten Sie, dass die Liste noch nicht sortiert ist, aber die Elemente befinden sich näher an den Positionen, an denen sie sich befinden sollten. Nachdem Sie die Einfügesortierung für diese Listenkombination durchgeführt haben, wird die Liste schließlich sortiert:
[2, 4, 6, 7, 16, 30, 39, 42, 51]
Algorithmusanalyse
Die Komplexität der Shell-Sortierung liegt zwischen O(n) und O(n2). Die Berechnung für diese Schlussfolgerung würde den Rahmen dieses Artikels sprengen.
Python-Implementierung:
def shellSort(my_list):
n = len(my_list)
interval = n // 2 # floor division
while interval > 0:
for val in range(interval, n):
temp = my_list[val]
x = val
while x >= interval and my_list[x - interval] > temp:
my_list[x] = my_list[x - interval]
x = x - interval
my_list[x] = temp
interval = interval // 2Weiter zur Zusammenführungssortierung
Es gibt mehrere Sortieralgorithmen, jeder mit einer einzigartigen Arbeitsweise. Die Merge-Sortierung verwendet beispielsweise eine Divide-and-Conquer-Strategie und hat eine Komplexität von O(nlogn).
Merge-Sort ist in einigen Fällen besser als Shell-Sort und auf jeden Fall einen Blick wert. Es sollte als nächstes auf Ihrer Leseliste für Sortieralgorithmen stehen.