Insertsort, Variante 5

Hierbei handelt es sich um eine alternative, optimierte Variante. Die Idee ist einfach: Eine binäre Suche benötigt deutlich weniger Vergleiche, als eine sequentielle.

Leider ändert sich die asymtotische Laufzeit nicht, da die Vertauschungen nicht optimiert werden können und Verschiebungen nicht möglich sind.

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

insertsort(field A, int l, int r) {
  for i:=l+1 to r do {
    q:= insert(A, l, i-1, i);
    move(A[i], A[q]);
  }
}

int insert(field A, int l, int r, int i) {
  while (l <= r) do {
    q:= (l+r) div 2;
    if (A[q] > A[i]) then {
      r:= q-1;
    } else {
      l:= q+1;
    }
  }
  return l;
}

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

insertsort(field A, int l, int r) {
  if (l < r) then {
    insertsort(A, l, r-1);
    q:= insert(A, l, r-1, r);
    move(A[r], A[q]);
  }
}

int insert(field A, int l, int r, int i) {
  if (l <= r) then {
    q:= (l+r) div 2;
    if (A[q] > A[i]) then {
      return insert(l, q-1, i);
    } else {
      return insert(q+1, r, i);
    }
  } else {
    return l;
  }
}


Insertsort, Variante 5