Robert Sedgewick: Algorithmen

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


8. Elementare Sortierverfahren



Selection Sort

Einer der einfachsten Sortieralgorithmen läuft wie folgt ab: Finde zuerst das kleinste Element im Feld und tausche es gegen das an der ersten Stelle befindliche Element aus, finde danach das zweitkleinste Element und tausche es gegen das an zweiter Stelle befindliche Element aus und fahre in dieser Weise fort, bis das gesamte Feld sortiert ist. Diese Methode wird Selection Sort (Sortieren durch (direktes) Auswählen) genannt, da sie darin besteht, daß wiederholt das kleinste verbliebene Element »ausgewählt« wird, wie in Abbildung 8.1 dargestellt ist. Der erste Durchlauf hat keine Wirkung, weil im Feld kein Element existiert, das kleiner als das links stehende A ist. Beim zweiten Durchlauf ist das zweite A das kleinste verbliebene Element, daher wird es gegen das an zweiter Stelle stehende S ausgetauscht. Danach wird beim dritten Durchlauf das erste E gegen das an dritter Stelle befindliche O ausgetauscht, danach beim vierten Durchlauf das zweite E gegen das an vierter Stelle stehende R usw.

Abbildung 8.1
Abbildung 8.1 Selection Sort.

Das folgende Programm ist eine vollständige Implementation dieses Prozesses. Für jedes i von 1 bis N - 1 tauscht es das kleinste Element in a[i..N] gegen a[i] aus:

    procedure selection;
      var i,j,min,t: integer;
      begin
      for i:=1 to N-1 do
        begin
        min:=i;
        for j:=i+1 to N do
          if a[j]<a[min] then min:=j;
        t:=a[min]; a[min]:=a[i]; a[i]:=t
        end;
      end;

Während der Zeiger i von links nach rechts durch die Datei wandert, befinden sich die Elemente links vom Zeiger auf ihrer endgültigen Position im Feld (und werden nicht wieder berührt), so daß das Feld vollständig sortiert ist, wenn der Zeiger das rechte Ende erreicht.

Dies ist eine der einfachsten Sortiermethoden, und sie ist für kleine Dateien sehr gut brauchbar. Die »innere Schleife« ist der Vergleich a[j] < a[min] (plus der Code, der benötigt wird, um j zu inkrementieren und zu überprüfen, ob es N nicht übersteigt), der kaum einfacher sein könnte. Weiter unten erörtern wir, wie oft diese Anweisungen voraussichtlich ausgeführt werden müssen.

Weiterhin hat Selection Sort, obwohl es offenbar eine »gewaltsame« Verfahrensweise ist, tatsächlich eine sehr wichtige Anwendung: Da jedes Element wirklich höchstens einmal bewegt wird, ist Selection Sort die bevorzugte Methode, um Dateien mit sehr großen Datensätzen und kleinen Schlüsseln zu sortieren. Dies wird noch im einzelnen betrachtet.


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