|
Der Insertion Sort ist langsam, weil nur benachbarte Elemente ausgetauscht werden. Wenn sich zum Beispiel das kleinste Element zufällig am Ende des Feldes befindet, so werden N Schritte benötigt, um es dorthinzubekommen, wo es hingehört. Shellsort ist einfach eine Erweiterung von Insertion Sort, bei dem eine Erhöhung der Geschwindigkeit dadurch erzielt wird, daß ein Vertauschen von Elementen ermöglicht wird, die weit voneinander entfernt sind.
Der Grundgedanke besteht darin, die Datei so umzuordnen, daß sie die Eigenschaft besitzt, daß man eine sortierte Datei erhält, wenn man jedes h-te Element (bei beliebigen Anfangselement) entnimmt. Eine solche Datei wird h-sortiert genannt. Mit anderen Worten, eine h-sortierte Datei besteht aus h unabhängigen sortierten Dateien, die einander überlagern. Durch das h-Sortieren für große h können wir Elemente im Feld über größere Entfernungen bewegen und damit ein h-Sortieren für kleinere Werte von h erleichtern. Indem man eine solche Prozedur für eine beliebige Folge von Werten von h anwendet, die mit 1 endet, erhält man eine sortierte Datei: dies ist Shellsort.
Shellsort ist die bevorzugte Methode für viele Anwendungen des Sortierens, da es selbst für relativ große Dateien (etwa bis zu 5000 Elementen) eine akzeptable Laufzeit aufweist und nur ein sehr kurzes Programm erfordert, daß sich leicht zu laufen bringen läßt. Kurz gesagt, wenn es ein Sortierproblem zu lösen gibt verwenden wir grundsätzlich immer dieses Programm und entscheiden dann, ob sich zusätzlicher Aufwand lohnen würde, es durch ein kompliziertes Verfahren zu ersetzen.
Laufzeit:
Der Shellsort führt niemals mehr als Vergleiche aus (für die Distanzen 1, 4, 13, 40, 121, .).
Es ist allerdings möglich, den Shellsort mit anderen Folgen von Distanzen noch effizienter zu machen. Doch ist es selbst für relativ große N schwer, das Programm um mehr als 20% schneller zu machen.
Funktionsweise:
Es wird eine Schrittreihenfolge gewählt (z.B.: 13-h). Vom ersten Element ausgehend wird jedes h-te Element herausgenommen und in die richtige Reihenfolge gebracht. Dieser Vorgang wird mit jedem Element durchgemacht bis man am Ende angelangt ist. Dann wird eine neue Schrittreihenfolge gewählt (kleiner als die erste z.B.: 5-h) und der Prozess beginnt von vorne.
Beschreibung:
1. Durchgang: Schrittreihenfolge 5 wird gewählt. Es wird das 1. und das 6. Element verglichen und da sie sich in der richtigen Reihenfolge befinden wird nichts verändert. Es wird das 2. und das 7. Element verglichen und da sie sich nicht in der richtigen Reihenfolge befinden werden sie vertauscht. Es wird das 3. und das 8. Element verglichen und da sie sich in der richtigen Reihenfolge befinden wird nichts verändert. u.s.w. . bis am Ende angelangt
2. Durchgang: Schrittreihenfolge 3 wird gewählt. Es wird das 1. und das 4. Element verglichen und da sie sich in der richtigen Reihenfolge befinden wird nichts verändert. Es wird das 2. und das 5. Element verglichen und da sie sich nicht in der richtigen Reihenfolge befinden werden sie vertauscht. u.s.w. .bis am Ende angelangt
u.s.w. . bis das Feld sortiert ist
|
