Robert Sedgewick: Algorithmen

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


8. Elementare Sortierverfahren



Exkurs: Bubble Sort

Ein elementares Sortierverfahren, das in einführenden Kursen oft gelehrt wird, ist Bubble Sort (Sortieren durch (direktes) Austauschen): Durchlaufe immer wieder die Datei und vertausche jedesmal, wenn es notwendig ist, benachbarte Elemente; wenn bei einem Durchlauf kein Austausch mehr erforderlich ist, ist die Datei sortiert. Eine Implementation des Verfahrens wird nachfolgend angegeben.

    procedure bubble;
      var i,j,t: integer;
      begin
      for i:=N downto 1 do
        for j:=2 to i do
          if a[j-1]>a[j] then
            begin t:=a[j-1]; a[j-1]:=a[j]; a[j]:=t end
      end;

Man muß etwas nachdenken, um sich davon zu überzeugen, daß dieser Weg überhaupt zum Ziel führt. Hierzu bemerken wir, daß jedesmal, wenn während des ersten Durchlaufs das maximale Element vorgefunden wird, dieses mit jedem der rechts von ihm befindlichen Elemente vertauscht wird, und dies so lange, bis es die Position am rechten Ende des Feldes erreicht hat. Während des zweiten Durchlaufs wird dann das zweitgrößte Element an die richtige Position bewegt usw. Somit läuft Bubble Sort wie eine Abart des Selection Sort ab, obwohl viel mehr Aufwand getrieben wird, um jedes Element an die richtige Position zu bringen.


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