Bubblesort, Variante 4 (Listen-Optimierung)

Hierbei handelt es sich um eine alternative Variante, die besonders für Listen geeignet ist. Auch hier ist die Idee simpel: Da bei Listen Verschiebungen billiger als Vertauschungen sind, wird der Algorithmus dem entsprechend angepaßt. Dadurch werden sogar Bewegungsoperationen eingespart, so daß es sich nicht nur um eine Alternative, sondern um eine Optimierung handelt.

Analog zur Variante 1 kann nun ebenfalls eine entsprechende Variante 2 bzw. 3 entwickelt werden.

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

bubblesort(list A, int l, int r) {
  for i:=r downto l+1 do {
    q:= l;
    for j:=l to i-1 do {
      if (A[j+1] > A[q]) then {
        move(A[q], A[j]);
        q:= j+1;
      }
    }
    move(A[q], A[i]);
  }
}

Variante 4.b (rekursiv)
Typ alternativ, optimiert
Eigenschaften rekursiv, in-place, stabil, nicht parallelisierbar
Datenstrukturen einfachverkettete Listen, Felder
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit Ω(n) Θ(n²) Ο(n²)
Vergleiche n²/2 n²/2 n²/2
Verschiebungen 0 n²/12 n²/2

bubblesort(field A, int l, int r) {
  if (l < r) then {
    bubble(A, l, l, r);
    bubblesort(A, l, r-1);
  }
}

bubble(field A, int q, int l, int r) {
  if (l < r) then {
    if (A[l+1] > A[q]) then {
      move(A[q], A[l]);
      q:= l+1;
    }
    bubble(A, q, l+1, r);
  } else {
    move(A[q], A[r]);
  }
}


Bubblesort, Variante 4