Bubblesort, Variante 2 (vorzeitiger Abbruch)

Hierbei handelt es sich um eine geringfügig verbesserte Variante. Die Idee ist einfach: Wenn keine einzige Vertauschung mehr nötig ist, so ist das Feld fertig sortiert. Weitere Vergleiche würden keine neuen Erkenntnisse bringen. Der Algorithmus kann vorzeitig beendet werden (vorzeitiger Abbruch). Im Normalfall ist der Gewinn minimal.

Variante 2.a (iterativ)
Typ optimiert
Eigenschaften iterativ, in-place, stabil, nicht parallelisierbar
Datenstrukturen Felder, einfachverkettete Listen
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit Ω(n) Θ(n²) Ο(n²)
Vergleiche n n²/2 n²/2
Vertauschungen 0 n²/4 n²/2

bubblesort(field A, int l, int r) {
  for i:=r downto l+1 do {
    flipped:= false;
    for j:=l to i-1 do {
      if (A[j] > A[j+1]) then {
        exchange(A[j], A[j+1]);
        flipped:= true;
      }
    }
    if (not flipped) then {
      return;
    }
  }
}

Variante 2.b (rekursiv)
Typ optimiert
Eigenschaften rekursiv, in-place, stabil, nicht parallelisierbar
Datenstrukturen Felder, einfachverkettete Listen
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit Ω(n) Θ(n²) Ο(n²)
Vergleiche n n²/2 n²/2
Vertauschungen 0 n²/4 n²/2
bubblesort(field A, int l, int r) {
  if (l < r) then {
    if bubble(A, l, r) then {
      bubblesort(A, l, r-1);
    }
  }
}

boolean bubble(field A, int l, int r) {
  if (l < r) then {
    if (A[l] > A[l+1]) then {
      exchange(A[l], A[l+1]);
      flipped:= true;
    } else {
      flipped:= false;
    }
    return bubble(A, l+1, r) or flipped;
  }
}


Bubblesort, Variante 2