Simplesort, Variante 3 (Listen-Optimierung)

Hierbei handelt es sich um eine alternative Variante, die besonders für Listen geeignet ist. Auch hier ist die Idee einfach: 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 könnte nun ebenfalls eine entsprechende Variante 3 aus Bubblesort entwickelt werden.

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

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

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

simplesort(field A, int l, int r) {
  if (l < r) then {
    do pipelined {
      simple(A, l, r);
      simplesort(A, l, r-1);
    }
  }
}

simple(field A, int l, int r) {
  if (l < r) then {
    if (A[l] > A[r]) then {
      move(A[l], A[r]);
      l--;
    }
    simple(A, l+1, r);
  }
}


Simplesort, Variante 3