Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


8. Elementare Sortierverfahren



Shellsort

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 dort hinzubekommen, wo es hingehört. Shellsort ist eine einfache 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 beliebigem 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.

Abbildung 8.7 zeigt die Arbeitsweise von Shellsort anhand unserer Beispieldatei mit den Distanzen . . . , 13, 4, 1. Beim ersten Durchgang wird das A auf Position 1 mit dem L auf Position 14 verglichen, wonach das S auf Position 2 mit dem E auf Position 15 verglichen (und ausgetauscht) wird. Beim zweiten Durchgang werden die Elemente A T E P auf den Positionen 1, 5, 9 und 13 derart umgeordnet, daß A E P T auf diese Positionen gesetzt werden, analog wird mit den Positionen 2, 6, 10 und 14 verfahren usw. Der letzte Durchgang ist ein einfaches Insertion Sort, doch kein Element muß sehr weit bewegt werden.

Abbildung 8.7
Abbildung 8.7 Shellsort.

Eine Möglichkeit zur Implementierung von Shellsort bestünde darin, für jedes h Insertion Sort unabhängig für jede der h Teildateien zu benutzen. (Marken würden nicht verwendet werden, denn man benötigte h (für den größten auftretenden Wert von h) von ihnen.) Doch es zeigt sich, daß es viel einfacher geht: Wenn wir in Insertion Sort jedes Auftreten von »1« durch »h« (und »2« durch »h+1«) ersetzen, realisiert das sich ergebende Programm ein h-Sortieren der Datei:

    procedure shellsort;
      label 0;
      var i,j,h,v: integer;
      begin
      h:=1; repeat h:=3*h+1 until h>N;
      repeat
        h:=h div 3;
        for i:=h+1 to N do
        begin
          v:=a[i]; j:=i;
          while a[j-h]>v do
            begin
            a[j]:=a[j-h]; j:=j-h;
            if j<=h then goto 0
            end;
          0: a[j]:=v
        end
      until h=1;
      end;

Dieses Programm verwendet die Distanzen-Folge ..., 1093, 364, 121, 40, 13, 4, 1. Andere Folgen von Distanzen können in der Praxis etwa mit dem gleichen Erfolg wie diese verwendet werden, doch wie unten dargelegt wird, ist eine gewisse Sorgfalt erforderlich. Die Abbildung 8.8 zeigt dieses Programm in seiner Anwendung auf eine zufällige Permutation, wobei der Inhalt des Feldes a nach jedem h-Sortieren dargestellt ist.

Abbildung 8.8
Abbildung 8.8 Sortieren einer zufälligen Permutation mittels Shellsort.

Die Folge der Distanzen in diesem Programm ist einfach in der Anwendung und führt zu einem effizienten Sortieren. Viele andere Folgen von Distanzen führen zu einem noch effizienteren Sortieren (der Leser könnte sich mit der Suche nach einer solchen Folge beschäftigen), doch es ist selbst für relativ große N schwer, das obige Programm um mehr als 20% zu übertreffen. (Die Möglichkeit, daß weit bessere Folgen von Distanzen existieren, ist jedoch dennoch gegeben.) Andererseits gibt es einige schlechte Folgen von Distanzen. Shellsort wird manchmal implementiert, indem bei h=N begonnen wird (anstatt es, wie oben, so zu initialisieren, daß gewährleistet wird, daß jedesmal die gleiche Folge benutzt wird). Damit wird praktisch garantiert, daß für bestimmte N eine schlechte Folge auftritt.

Die obige Beschreibung der Effizienz von Shellsort ist notwendigerweise ungenau, da noch niemand in der Lage war, den Algorithmus zu analysieren. Dadurch wird es nicht nur schwierig, verschiedene Folgen von Distanzen zu beurteilen, sondern auch, Shellsort analytisch mit anderen Methoden zu vergleichen. Nicht einmal der funktionale Ausdruck für die Laufzeit ist für Shellsort bekannt (außerdem ist seine Gestalt von der Folge der Distanzen abhängig). Für das obige Programm lauten zwei Vermutungen N (log N)2 und N1,25. Die Laufzeit ist nicht sonderlich abhängig von der ursprünglichen Ordnung in der Datei, im Gegensatz etwa zu Insertion Sort, welches für eine bereits geordnete Datei linear, für eine in umgekehrter Reihenfolge angeordnete Datei jedoch quadratisch ist. Abbildung 8.9 zeigt die Arbeitsweise von Shellsort für eine in umgekehrter Reihenfolge angeordnete Datei.

Abbildung 8.9
Abbildung 8.9 Sortieren einer in umgekehrter Reihenfolge angeordneten Permutation mittels Shellsort.

Eigenschaft 8.6 Shellsort führt niemals mehr als N3/2 Vergleiche aus (für die Distanzen 1, 4, 13, 40, 121,...).

Der Beweis dieser Eigenschaft würde über den Rahmen dieses Buches hinausführen. Der Leser soll jedoch nicht nur seine Schwierigkeit anerkennen, sondern sich auch davon überzeugen, daß Shellsort in der Praxis effizient abläuft, indem er versucht, eine Datei zu konstruieren, für die Shellsort langsam abläuft. Wie oben erwähnt wurde, gibt es einige ungünstige Folgen von Distanzen, für die Shellsort eine quadratische Anzahl von Vergleichen benötigen kann, doch es ist gezeigt worden, daß die Schranke N3/2 für eine Vielzahl von Folgen gilt (einschließlich der oben benutzten Folge). Für einige spezielle Folgen sind sogar noch bessere Schranken für den ungünstigsten Fall bekannt. w.z.b.w.

Abbildung 8.10, die die Arbeitsweise von Shellsort von einem anderen Blickwinkel aus zeigt, kann mit den Abbildungen 8.3, 8.4 und 8.5 verglichen werden. Diese Abbildung zeigt den Inhalt des Feldes nach jedem h-Sortieren (mit Ausnahme des letzten, welches das Sortieren vollendet). Bei diesen Bildern könnten wir uns ein Gummiband vorstellen, das in der linken unteren und rechten oberen Ecke befestigt ist und immer straffer gespannt wird, um alle Punkte zur Diagonale hin zu bewegen. Die drei Bilder der Abbildungen 8.3, 8.4 und 8.5 repräsentieren jeweils eine beträchtliche Menge an Arbeit, die vom dargestellten Algorithmus verrichtet wurde; im Gegensatz dazu stellt jedes der Bilder von Abbildung 8.10 nur einen Durchgang des h-Sortierens dar.

Abbildung 8.10
Abbildung 8.10 Sortieren einer zufälligen Permutation mittels 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, das sich leicht zum Laufen bringen läßt. Wir werden in den nachfolgenden Kapiteln Verfahren kennenlernen, die effizienter, doch (außer für große N) bestenfalls doppelt so schnell und bedeutend komplizierter sind. Kurz gesagt, wenn Sie ein Sortierproblem zu lösen haben, verwenden Sie obiges Programm, und entscheiden Sie dann, ob sich der zusätzliche Aufwand lohnen würde, es durch ein kompliziertes Verfahren zu ersetzen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]