Insertsort, Variante 3 (Listen-Optimierung)

Hierbei handelt es sich um eine alternative Variante (Alternative zu Variante 2!), 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 um eine echte Optimierung handelt.

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

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

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

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

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


Insertsort, Variante 3