Insertsort, Variante 2 (Vergleichsreduzierung)

Hierbei handelt es sich um eine verbesserte Variante. Trotz dieser Verbesserung ist eine iterative Realisierung möglich (vgl. Bubblesort). Die Idee ist einfach: Wenn ein Element an der richtigen Stelle platziert wurde, dann ist der "Einfügevorgang" beendet.

Diese Variante läßt sich analog zu Variante 1 parallelisieren.

Diese Variante ist bekannter als die echte Standard-Variante. Wundern sie sich also nicht, wenn Ihnen woanders nur diese Variante geboten wird.

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

insertsort(field A, int l, int r) {
  for i:=l+1 to r do pipelined {
    j:= i;
    while ((j > l) and (A[j-1] > A[j])) do {
      exchange(A[j-1], A[j]);
      j--;
    }
  }
}

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

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

insert(field A, int l, int r) {
  if (l < r) and (A[r-1] > A[r]) then {
    exchange(A[r-1], A[r]);
    insert(A, l, r-1);
  }
}


Insertsort, Variante 2