|
Beschreibung
. Die Daten werden in einer doppelten Schleife abgearbeitet.
. Die innere Schleife umspannt jeweils den gesamten unsortierten Bereich: Dieser wird iterativ durchgearbeitet. Wenn ein Element größer ist als sein rechter Nachbar, so werden sie miteinander vertauscht.
. Nach jedem äußeren Schleifendurchlauf wurde der sortierte Bereich am Ende der Daten um mindestens 1 erhöht.
Programmcode
procedure BubbleSort ( var f : TArray; HighIndex : integer ) : string;
var i, j : integer;
begin
for i := HighIndex downto 1 // äußere Schleife
do for j := 0 to i
do if f[j] > f[j+1] then swap (f[j], f[j+1]); // innere Schleife
end; // BubbleSort
Aufwandsabschätzung
mittlerer-Aufwand:
. Die äußere Schleife wird n-1 mal durchlaufen.
. Die innere Schleife wird im Durchschnitt (n-1)/2 mal durchlaufen.
Daraus folgt der Aufwand .
worst-case-Aufwand:
Der maximale Aufwand beträgt ebenfalls O(n2), da beide Schleifen auch im schlechtesten Fall genauso oft durchlaufen werden. Der Unterschied ist nur die Anzahl der benötigten Tauschvorgänge (im besten Fall ist gar keiner nötig).
Sortierdauer
|
