bubblesort

Bubblesort

Funktionsweise

Der Algorithmus Bubblesort ist einer der bekanntesten Sortieralgorithmen und ist zudem recht einfach zu verstehen. Das Prinzip basiert darauf, dass systematisch alle Paare benachbarter Elemente miteinander verglichen werden. Ist ein Element größer als sein Nachfolger, so ist gegen das Ordnungsprinzip verstoßen und die beiden Elemente tauschen ihre Plätze. So wandern nach und nach die kleinen Elemente an den Anfang, die größeren hingegen an das Ende des Feldes. Nach hinreichend vielen solcher elementaren Vertauschungen haben schließlich alle Elemente ihren Platz in der richtigen Reihenfolge gefunden.
Der Name »Bubblesort« ergibt sich aus der Vorstellung von aufsteigenden Luftblasen, wobei die leichten Bläschen eben schneller an die Oberfläche gelangen als die schweren.

I =

J =

Stoppuhr:

Vergleiche =

Vertauschungen =

Variante 1: alle großen Elemente nach hinten sortieren
Das Feld wird zunächst aufsteigend (vollständig) durchlaufen. Ist ein Element größer als sein Nachfolger, so werden sie getauscht. Am Ende dieser ersten Schleife ist das größte Element an die letzte Stelle gewandert. Nun erfolgt der Durchlauf zum zweiten Male. Auf den Vergleich mit dem letzten Element kann jedoch verzichtet werden, da jenes ohnehin das größte ist. So gelangt das zweitgrößte Element an die vorletzte Stelle und so weiter. Bei jedem weiteren Durchlauf vermindert sich die Anzahl der notwendigen Vergleiche um 1, so dass das Sortieren immer schneller erfolgt.


procedure bubble(var zahl: feld);
var i,j,help: byte;
begin
  for i:=0 to size-1 do
  begin
    for j:=0 to size-1-i do
    begin
      if zahl[j]>zahl[j+1] then
      begin
        help:=zahl[j+1];
        zahl[j+1]:=zahl[j];
        zahl[j]:=help;
      end;
    end;
  end;
end;

procedure TForm1.btnSortClick(Sender: TObject);
begin
  bubble(zahl);
  printList(zahl);
end;

Variante 2: alle kleinen Elemente nach vorn sortieren
Lässt man die innere Schleife rückwärts laufen, so werden die kleineren Elemente an den Anfang des Feldes sortiert. Der Rest des Algorithmus ist identisch.


procedure bubble(var zahl: feld);
var i,j,help: byte;
begin
  for i:=0 to size-1 do
  begin
    for j:=size-1 downto i do
    begin
      if zahl[j]>zahl[j+1] then
      begin
        help:=zahl[j+1];
        zahl[j+1]:=zahl[j];
        zahl[j]:=help;
      end;
    end;
  end;
end;

procedure TForm1.btnSortClick(Sender: TObject);
begin
  bubble(zahl);
  printList(zahl);
end;