Robert Sedgewick: Algorithmen

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


8. Elementare Sortierverfahren



Insertion Sort

Ein Algorithmus, der fast genauso einfach wie Selection Sort, aber vielleicht flexibler ist, ist Insertion Sort (Sortieren durch (direktes) Einfügen). Dies ist die Methode, die Menschen oft beim Kartenspiel anwenden, um ihre Karten zu sortieren: Betrachte die Elemente eines nach dem anderen und füge jedes an seinen richtigen Platz zwischen den bereits betrachteten ein (wobei diese sortiert bleiben). Das gerade betrachtete Element wird eingefügt, indem die größeren Elemente einfach um eine Position nach rechts bewegt werden und das Element dann auf dem freigewordenen Platz eingefügt wird, wie Abbildung 8.2 zeigt. Das S auf der zweiten Position ist größer als das A, daher muß es nicht bewegt werden. Wenn das O auf der dritten Position vorgefunden wird, wird es gegen das S ausgetauscht, um A O S in eine sortierte Reihenfolge zu bringen usw.

Abbildung 8.2
Abbildung 8.2 Insertion Sort.

Dieser Prozeß ist im folgenden Programm implementiert. Für jedes i von 2 bis N wird das Unterfeld a[1..i] sortiert, indem a[i] an die entsprechende Stelle zwischen den Elementen in dem sortierten Unterfeld links von ihm gesetzt wird:

    procedure insertion;
      var i,j,v: integer;
      begin
      for i:=2 to N do
        begin
        v:=a[i]; j:=i;
        while a[j-1]>v do
          begin a[j]:a[j-1]; j:=j-1 end;
        a[j]:=v
        end
      end;

Wie bei Selection Sort sind die Elemente links vom Zeiger i während des Sortierens in einer sortierten Reihenfolge angeordnet, doch sie befinden sich nicht auf ihrer endgültigen Position, da sie möglicherweise bewegt werden müssen, um für später gefundene kleinere Elemente Platz zu machen. Das Feld ist jedoch vollständig sortiert, wenn der Zeiger das rechte Ende erreicht.

Es muß noch eine wichtige Einzelheit betrachtet werden: In der vorliegenden Form funktioniert die Prozedur insertion nicht, da die while-Anweisung über das linke Ende des Feldes hinaus läuft, wenn v das kleinste Element im Feld ist. Um Abhilfe zu schaffen, setzen wir einen »Marken«-Schlüssel (»sentinel«-key) auf a[0], den wir mindestens so klein wählen wie das kleinste Element im Feld. Marken werden gewöhnlich in Situationen wie dieser verwendet, um die Aufnahme eines nahezu immer positiv ausfallenden Tests (im vorliegenden Falle j>1) in die innere Schleife zu vermeiden.

Falls es aus irgendeinem Grund schwierig ist, eine Marke zu verwenden, und das Feld wirklich die Grenzen [1..N] haben muß, bietet Standard-Pascal keine saubere Alternative, da es keine »bedingte« and-Anweisung aufweist; in der vorliegenden Situation scheint der Test while (j>1) and (a[j-1]>v) angebracht zu sein, doch das funktioniert nicht, weil selbst dann, wenn j=1 ist, der zweite Teil der and-Bedingung berechnet wird und einen Zugriff auf das Feld außerhalb der Grenzen bewirkt. Eine goto-Anweisung zum Verlassen der Schleife scheint erforderlich zu sein. (Manche Programmierer ziehen es vor, einigen Aufwand in Kauf zu nehmen, um goto-Anweisungen zu vermeiden, zum Beispiel indem sie innerhalb der Schleife Vorkehrungen treffen, um zu gewährleisten, daß die Schleife abbricht. Im vorliegenden Fall scheint eine solche Lösung kaum gerechtfertigt zu sein, da sie das Programm nicht klarer macht und jedesmal über die Schleife Ballast hinzufügt, nur um für ein seltenes Ereignis abgesichert zu sein.)


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