Simplesort, Variante 2 (Alternativ,Original)

Hierbei handelt es sich um eine alternative Original-Variante, die jedoch hinsichtlich er Laufzeit einige schwächen aufweist.

Es wurde lediglich die Richtung der inneren for-Schleife umgekehrt.

Analog zu Bubblesort (Variante 3) sind hier ebenfalls einige Optimierungen möglich. Die Realisierung wäre jedoch etwas komplizierter.

Mit etwas Geschick ist diese Variante parallelisierbar. Genauere Informationen dazu finden sie in Variante 5.

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

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

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

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

simple(field A, int l, int j, int r) {
  if (l <= i) then {
    if (A[i] > A[r]) then {
      exchange(A[i], A[r]);
    }
    simple(A, l, i-1, r);
  }
}


Simplesort, Variante 2