Shellsort
ShellSort ist ein von Donald L. Shell im Jahre 1959 entwickelter Sortieralgorithmus, der auf dem Sortieralgorithmus des direkten Einfügens (Insertionsort) basiert.
Prinzip
Der Gedanke, der hinter ShellSort steht kann wie folgt beschrieben werden:
- Die Daten werden in eine zweidimensionale Matrix geschrieben
- Die Spalten der Matrix werden einzeln sortiert
Daraus resultiert eine grobe Sortierung. Dieser Schritt wird öfters wiederholt, wobei jeweils die Breite der Matrix verringert wird, bis die Matrix nurnoch aus einer einzigen vollständig sortierten Spalte besteht.
ShellSort arbeitet instabil und in-place.
Beispiel
Zu sortieren sind die Zahlen: 2 5 3 4 3 9 3 2 5 4 1 3
Zuerst werden die Daten in eine Matrix mit 4 Spalten eingetragen und spaltenweise sortiert.
2 5 3 4 2 4 1 2 3 9 3 2 -> 3 5 3 3 5 4 1 3 5 9 3 4
Die sortierte 4-Spalten-Matrix wird nun in zwei Spalten aufgeteilt. Diese Spalten werden nun sortiert.
2 4 1 2 1 2 2 3 3 5 -> 3 4 3 3 3 4 5 9 3 5 3 4 5 9
Die sortierte 2-Spalten-Matrix wird nun in eine Spalte geschrieben und wieder sortiert.
1 2 2 3 3 4 3 4 3 5 5 9 -> 1 2 2 3 3 3 3 4 4 5 5 9
Implementierung
Tatsächlich werden die Daten nicht in Form einer Matrix, sondern in Form eines eindimensionalen Feldes angeordnet. Die Spalten werden durch geschickte Indizierung gebildet. So bilden alle Elemente im Abstand h eine Spalte. Diese Spalten werden per (Insertionsort) sortiert, da dieser Algorithmus von einer Vorsortierung der Daten profitieren kann.
Komplexität
Die Komplexität von Shellsort hängt von der Wahl der Folge für die Spaltenanzahl h ab. Mit der Folge 1, 3, 7, 15, 31, 63, ..., 2k - 1 wird eine Komplexität von O(n1,5) erreicht. Mit der Folge 1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2p3q ist die Komplexität O(n·log(n)2). Eine Folge für O(n·log(n)) scheint jedoch nicht zu existieren. Es wurde experimentell belegt, dass die allgemeine Komplexität in O(n1.25) liegt.
Literatur
- Donald L. Shell: A High-Speed Sorting Procedure. Commun. ACM 2(7): 30-32 (1959).