Bubble-Sort = Sortieren durch Austauschen (fakultativ)

Hier werden die Folge n-1 mal rückwärts beginned durchlaufen und dabei benachbarte Elemente ausgetauscht.

Steht also eine größere Zahl vor einer kleineren Zahl, so werden die beiden miteinander vertauscht. Dies wird so lange wiederholt, bis keine Vertauschung mehr notwendig ist, bis also das Array nicht mehr geändert wird.
Die Laufzeit steigt mit der Anzahl zu sortierender Elemente quadratisch an - bei jedem Durchlauf müssen alle Elemente jeweils mit einem anderen verglichen werden.

In Animationen dazu verwendet man für die wie im Wasser nach oben steigenden größeren Elemente gern Blasen.

 

Links

Delphi

Erläuterung und Animation
Erläuterung und Java-Code Animation 1,
Animation 2,

Pseudocode


procedure bubblesort ( var a : sequence );
var i : integer ;
begin
  repeat
    for i :=1 to (n - 1) do
    if a [ i ]. key > a [ i + l]. key
    then { vertausche a [ i ] und a [ i + 1]}
  until { Vertauschung beendet }
end

Komplexität