Vorlesung Informatik 2 - Teil B: Theorie
2.5 Shell Sort
Donald Shell entwickelte 1959 einen Algorithmus, der zu ersten Mal die Komplexität O(N2) brach. Er arbeitete bei General Electric mit einem IBM 704 Computer mit einen für die damalige Zeit extrem großen Hauptspeicher von ca. 32.000 Worten. Sein Artikel in der Fachzeitschrift "Communications of the ACM" ist gerade mal 3 Seiten lang...
Er erkannte, dass Sortierung umso effizienter ist, je größer die Distanzen sind, zwischen denen Element getauscht werden.
Die Daten werden in Untersequenzen aufgeteilt, deren Elemente den gleichen Abstand innerhalb der Originaldaten voneinander haben. Diese Sequenzen werden durch Insertion-Sort sortiert.
Donald Shell nutzt im ersten Schritt den Abstand N/2, also werden N/2 Untersequenzen der Länge 2 (und eventuell eine der Länge 3) erzeugt, Deren Sortierung ist trivial, da nur zwei Werte verglichen werden müssen.
Im nächsten Schritt werden Sequenzen mit einem Abstand von N/4 erzeugt und sortiert. dann N/8 usw., bis wir 1 erreichen. Bei der Division wird immer abgeschnitten, so wie bei jeder Integer-Division im Computer.
Die Folge N/2, N/4, N/8, ... heißt Distanzfolge, ihre Bildungsregel lautet N/2i
Beispiel: wir sortieren11 Zahlen, also arbeiten wir mit der Distanzfolge 11/2, 11/4 und 11/8 , also 5, 2 und 1:
Schritt 1: die farbig markierte Untersequenzen haben jeweils einen Abstand von 5:
42
33 21
44
16 11
51 14 36 38 10 bis auf die rote Sequenz haben alle nur eine Länge von 2
Jetzt sortieren wir jede de farbigen Sequenzen für sich, dabei wird über eine Distanz von 5 getauscht:
10 33
14 36 16 11 51
21 44 38
42 man nennt die Daten jetzt 5-sortiert
Schritt 2: Aufteilung in Untersequenzen mit einem Abstand von 2:
10
33 14 36
16
11 51 21
44
38 42 die beiden Sequenzen sind teilweise Sortiert, davon profitiert der Insertion-Sort
Durch Sortieren der grünen und der roten Sequenz erhalten wir folgende Zahlen:
10
11 14
21 16 33
42 36
44 38 51
Schritt 3: ein Insertion-Sort des ganzen Arrays, der massiv davon profitiert, dass die Folge schon teilsortiert ist - probieren Sie es aus.
Ein wichtiger Aspekt des Shell-Sort ist die Distanzfolge. Im obigen Beispiel war k=4, dann 2 und dann 1.
Die von Donald Shell vorgeschlagene Folge von Distanzen k mit der Bildungsregel sieht folgendermaßen aus:
k0=N/2
k1 = k0/2
..
ki+1=ki/2
Wenn wir also 1000 Zahlen mit dieser Distanzfolge sortieren haben wir zunächst der Abstand 500, dann 250, dann 125, 62 usw. Diese Folge führt zu einer Komplexität von O(N3/2), vorausgesetzt N ist keine Potenz von 2.
Bis heute beschäftigen sich die Informatiker mit der Frage, welches die optimale Distanzfolge ist.
Thomas Hibbard schlug 1963 die einfachere Folge 2k-1 vor, die immer O(N3/2) garantiert.
Der Computer-Pionier Donald Knuth hat 1973 mit (3k-1)/2 eine weitere O(N3/2) Distanzfolge veröffentlicht.
Robert Sedgewick fand 1982 die Reihe 4k+3·2k-1+1 und konnte beweisen, dass sie die Komplexität O(N4/3) garantiert.
Marcin Ciura schlug 2001 eine experimentell abgeleitete Folge 1,2,10,23,57,132,302,701,... vor, konnte aber keine Komplexität dafür angeben (in der Antike hätte es dafür den Schierlingsbecher gegeben).
In den Beispielen finden Sie die Klasse ShellSort, in der ich die Distanzfolgen von Shell, Hibbard und Sedgewick implementiert habe, die das unterschiedliches Laufzeitverhalten demonstriert - probieren Sie es selbst aus.
Der Shell-Sort Algorithmus ist nicht stabil aber arbeitet in-situ.