StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
Americas
Europe
Bei dem Begriff "Shell" denkst Du vermutlich als Erstes an die deutsche Übersetzung "Muschel" – was teilweise sicherlich auch der Tankstelle geschuldet ist, die das Symbol neben ihrem Namen als Logo verwendet. Mit Shell Sort haben jedoch beide absolut gar nichts zu tun. Stattdessen handelt es sich bei Shell Sort um einen Sortieralgorithmus. Was dabei die Besonderheiten sind und wie der Algorithmus…
Entdecke über 200 Millionen kostenlose Materialien in unserer App
Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken
Jetzt kostenlos anmeldenBei dem Begriff "Shell" denkst Du vermutlich als Erstes an die deutsche Übersetzung "Muschel" – was teilweise sicherlich auch der Tankstelle geschuldet ist, die das Symbol neben ihrem Namen als Logo verwendet. Mit Shell Sort haben jedoch beide absolut gar nichts zu tun.
Stattdessen handelt es sich bei Shell Sort um einen Sortieralgorithmus. Was dabei die Besonderheiten sind und wie der Algorithmus funktioniert, erfährst Du hier.
Der Shell Sort oder auch Shellsort Algorithmus basiert auf Insertion Sort, ist jedoch das schnellere Verfahren. Das Grundprinzip ist es, Datenmengen in Teilmengen zu zerlegen und diese mit Insertion Sort zu sortieren. Dadurch erhältst Du bei jedem Iterationsschritt eine neue Grobsortierung. Die Teilmengen werden mit jedem Schritt kleiner, bis Du schließlich eine vollständig sortierte Liste bekommst.
Shell Sort wurde 1959 von Donald. L. Shell entwickelt.
Shell Sort ist ein instabiler, vergleichsbasierter Sortieralgorithmus, der Datenmengen iterationsweise in unterschiedlich große Teilbereiche zerlegt und diese immer wieder mit Insertion Sort sortiert.
Wie Du bei Shellsort vorgehst, lässt sich am besten an einem Beispiel zeigen. Gegeben ist folgendes Array:
5 | 2 | 8 | 4 | 9 | 7 | 2 | 3 |
Das Grundprinzip bei Shellsort ist es, eine Datenmenge in kleinere Teilmengen zu zerteilen. Die Länge der Teilmenge bestimmt dabei die Laufzeit des Algorithmus mit – Du solltest die einzelnen Teilbereiche also weder zu groß noch zu klein wählen.
In diesem Beispiel werden die Längen 4, 2 und 1 gewählt.
Die Länge der Teilmenge wird im englischen häufig als "gap" oder "interval" bezeichnet. Auch im Deutschen kannst Du den Begriff Intervall oder Intervall-Länge verwenden.
Im ersten Durchlauf wird das Array in zwei Arrays mit jeweils einer Länge von 4 geteilt. Diese schreibst Du am besten untereinander – das macht es übersichtlicher.
5 | 2 | 8 | 4 |
9 | 7 | 2 | 3 |
Jetzt sortierst Du die einzelnen Spalten nach dem Insertion Sort – also von oben nach unten. Dabei musst Du die 8 und die 2 und die 4 mit der 3 vertauschen.
5 | 2 | 2 | 3 |
9 | 7 | 8 | 4 |
Anschließend fügst Du die Teilbereiche wieder zu einem Array zusammen:
5 | 2 | 2 | 3 | 9 | 7 | 8 | 4 |
Nun kommt der zweite Durchlauf, wobei diesmal die Länge 2 für die Teillisten gewählt wird. Auch diese Teillisten schreibst Du wieder untereinander und sortierst sie spaltenweise mit Insertion Sort.
5 | 2 |
2 | 3 |
9 | 7 |
8 | 4 |
Nach dem Sortieren erhältst Du folgendes Zwischenergebnis.
2 | 2 |
5 | 3 |
8 | 4 |
9 | 7 |
Dieses führst Du wieder zu einer Gesamtliste zusammen.
2 | 2 | 5 | 3 | 8 | 4 | 9 | 7 |
Beim dritten Durchlauf wählst Du jetzt eine Länge von 1 für die einzelnen Teilbereiche. Anders gesagt: Du sortierst die übrige Liste einfach mit Insertion Sort. Da die Liste schon teilweise vorsortiert ist, dauert das Sortieren hier in der Regel nicht mehr allzu lange.
Als Ergebnis erhältst Du nach den letzten Vertauschungen die sortierte Liste:
2 | 2 | 3 | 4 | 5 | 7 | 8 | 9 |
Und fertig ist Dein sortiertes Array nach Shell Sort!
Noch einmal kurz und knapp, wie gehst Du beim Shellsort Algorithmus vor:
Wie könnte ein mögliches Struktogramm bei Shell Sort aussehen?
Abb. 1 Struktogramm für Shell Short
Bei der Komplexität von Shell Sort müssen die Laufzeit (Zeitkomplexität) und der zusätzlich benötigte Speicher (Platzkomplexität) betrachtet werden.
Wie effizient Shell Sort ist, hängt stark von der Wahl der Länge der Teilmengen ab. Doch warum verwendet man überhaupt Shell Sort, wenn es sich dabei im Prinzip auch einfach nur um den Insertion Sort Algorithmus handelt? Durch die Grobsortierung des Shell Sort bekommst Du eine deutlich bessere Laufzeit als bei Insertion Sort.
Im Worst-Case, also bei einer eher schlecht gewählten Intervall-Länge, hat Shell Sort eine Laufzeit von O(n2),
Sowohl im Best-Case als auch im Average-Case hat Shell Sort hingegen eine Laufzeit von O(n log n).
Mehr zu den Unterschieden zwischen Shell Sort und Insertion Sort findest Du in einem eigenen Abschnitt weiter unten in dieser Erklärung.
Shellsort läuft in-place, also ohne zusätzlich benötigten Speicherplatz, ab. Somit ist die Platzkomplexität konstant und beträgt O(1).
Im Folgenden werden noch weitere wichtige Begriffe rund um Shellsort erläutert.
Durch das Unterteilen in Teilmengen und das Sortieren dieser Teillisten untereinander mit Insertion Sort, kann die ursprüngliche Reihenfolge bei gleichen Elementen nicht gewährleistet werden. Der Algorithmus ist also instabil.
Shell Sort ist ein vergleichsbasiertes Sortierverfahren, da immer zwei Elemente miteinander verglichen werden, um über ihre Anordnung in der Datenmenge zu entscheiden.
Im Gegensatz zum ursprünglichen Insertion Sort ist Shellsort parallelisierbar. Dafür lagerst Du die einzelnen Teilmengen im Grunde einfach auf Prozessoren aus. Dort werden die Daten parallel mit einem eigenen Shellsort sortiert. Anschließend fügst Du die sortierten Teilmengen wieder zu einer kompletten Liste zusammen, wobei die Daten noch mal abschließend sortiert werden.
Das bisher Gelernte findest Du hier auf einem Blick zusammengefasst:
Best-Case | Average-Case | Worst-Case | Platz-komplexität | Stabiles Verfahren | vergleichs-basiert | In-Place | Parallelisier-barkeit |
O(n log n) | O(n log n) | O(n2) | O(1) | Nein | Ja | Ja | Ja |
Shell Sort basiert auf dem Insertion Sort Sortierverfahren, was dabei die Unterschiede sind, kannst Du der folgenden Tabelle entnehmen. Wichtig zu wissen ist noch, dass Shell Sort grundsätzlich entwickelt wurde, um die Ineffizienz des Insertion Sorts zu verbessern. Ziel war es also, die große Anzahl an Vergleichen zu reduzieren.
Eigenschaften | Shell Sort | Insertion Sort |
Laufzeit | Best-Case: O(n log n)Average-Case: O(n log n)Worst-Case: O(n2) | Best-Case: O(n)Average-Case: O(n2)Worst-Case: O(n2) |
Platzkomplexität | O(1) | O(1) |
Stabilität | Instabiles Verfahren | Stabiles Verfahren |
Vergleichsbasiert | Ja | Ja |
Parallelisierbarkeit | Ja | Nein |
Vorteile | Benötigt weniger Tauschoperationen als Insertion Sort | Einfach zu implementieren |
Am effizientesten für mittelgroße Datenmengen | Algorithmus ist leicht verständlich | |
Nachteil | Effizienz ist stark abhängig vom gewählten Intervall | Ineffizient bei großen Datenmengen |
Genaueres zum Insertion Sort kannst Du in der gleichnamigen Erklärung auf StudySmarter nachlesen.
Nun folgen noch zwei Code-Beispiele für eine mögliche Implementierung – in Java könnte das wie folgt aussehen:
import java.util.Arrays; class ShellSort { // Elemente mit den Intervallen von n/2, n/4, n/8, ... neu anordnen void shellSort(int array[], int n) { for (int interval = n / 2; interval > 0; interval /= 2) { for (int i = interval; i < n; i += 1) { int temp = array[i]; int j; for (j = i; j >= interval && array[j - interval] > temp; j -= interval) { array[j] = array[j - interval]; } array[j] = temp; } } } // Treibercode public static void main(String args[]) { // zu sortierende Datenmenge eingeben int[] data = { 5, 2, 8, 4, 9, 7, 2, 3 }; int size = data.length; ShellSort ss = new ShellSort(); ss.shellSort(data, size); // Ausgabe hinzufügen System.out.println("Sortiertes Array: " " + Arrays.toString(data)); } }
Ausgabe:
Sortiertes Array: 2 2 3 4 5 7 8 9
In C könnte Shell Sort hingegen so implementiert werden.
Als Ergebnis erhältst Du wieder das gleiche sortierte Array wie bei der Java-Implementierung.
#includevoid shellSort(int array[], int n) { // Elemente mit den Intervallen von n/2, n/4, n/8, ... neu anordnen for (int interval = n / 2; interval > 0; interval /= 2) { for (int i = interval; i < n; i += 1) { int temp = array[i]; int j; for (j = i; j >= interval && array[j - interval] > temp; j -= interval) { array[j] = array[j - interval]; } array[j] = temp; } } } // Array ausgeben void printArray(int array[], int size) { for (int i = 0; i < size; ++i) { printf("%d ", array[i]); } printf("\n"); } // Treibercode int main() { int data[] = {5, 2, 8, 4, 9, 7, 2, 3}; int size = sizeof(data) / sizeof(data[0]); shellSort(data, size); printf("Sortiertes Array: \n"); printArray(data, size); }
Shell Sort ist kein stabiler Sortieralgorithmus, da nicht gewährleistet werden kann, dass die Reihenfolge gleicher Elemente beim Partitionieren und Sortieren erhalten bleibt.
Shell Sort teilt Datenmengen nach verschiedenen Intervall-Längen in Teilmengen auf und sortiert diese mit Insertion Sort solange, bis eine vollständig sortierte Liste entsteht.
Shell Sort ist ein instabiler, vergleichsbasierter Sortieralgorithmus, der Datenmengen iterationsweise in unterschiedlich große Teilbereiche zerlegt und diese immer wieder mit Insertion Sort sortiert.
Wie möchtest du den Inhalt lernen?
94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmelden94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmeldenWie möchtest du den Inhalt lernen?
Kostenloser informatik Spickzettel
Alles was du zu . wissen musst. Perfekt zusammengefasst, sodass du es dir leicht merken kannst!
Sei rechtzeitig vorbereitet für deine Prüfungen.
Teste dein Wissen mit spielerischen Quizzes.
Erstelle und finde Karteikarten in Rekordzeit.
Erstelle die schönsten Notizen schneller als je zuvor.
Hab all deine Lermaterialien an einem Ort.
Lade unzählige Dokumente hoch und habe sie immer dabei.
Kenne deine Schwächen und Stärken.
Ziele Setze dir individuelle Ziele und sammle Punkte.
Nie wieder prokrastinieren mit unseren Lernerinnerungen.
Sammle Punkte und erreiche neue Levels beim Lernen.
Lass dir Karteikarten automatisch erstellen.
Erstelle die schönsten Lernmaterialien mit unseren Vorlagen.
Melde dich an für Notizen & Bearbeitung. 100% for free.