Shellsort, Variante 4 (Knuth)

Hierbei handelt es sich um eine Beispielfolge. Die Folge von Knuth "1,4,13,40,121,364,1093,3280,9841,...,x" verspricht eine Laufzeit, die in Ω(nlogn) und Ο(n3/2) liegt. Jede Zahl ist das dreifache seines Nachfolgers plus eins (xp+1 = 3*xp+1 = 3p+1+xp, x <= (r-l+1)/2). Diese Folge wird sehr häufig angewendet, liefert bei kleinem n das beste Ergebnis und ist hinsichtlich der Laufzeit der Sedgewick-Folge sehr ähnlich jedoch leichter zu berechnen.

Variante 4.a (iterativ)
Typ Beispiel
Eigenschaften iterativ, in-place, instabil, parallelisierbar
Datenstrukturen Felder
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit (p) Ω(n) Θ(???) Ο(???)
Laufzeit Ω(nlogn) Θ(n(logn)1.7) Ο(n3/2)
Vergleiche nlogn/1.58 n(logn)1.6/2.80 ???
Vertauschungen 0 n(logn)1.7/5.34 ???

shellsort(field A, int l, int r) {
  step:= 1;
  while (step <= r-l) do { 
    step:= step*3+1;
  }
  do {
    step:= (step-1)/3;
    for i:=0 to step-1 do parallel {
      insertsort(A, l+i, r, step);
    }
  } while (step > 1);
}

insertsort(field A, int l, int r, int step) {
  ...
}

Variante 4.b (rekursiv)
Typ Beispiel
Eigenschaften rekursiv, in-place, instabil, parallelisierbar
Datenstrukturen Felder
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit (p) Ω(n) Θ(???) Ο(???)
Laufzeit Ω(nlogn) Θ(n(logn)1.7) Ο(n3/2)
Vergleiche nlogn/1.58 n(logn)1.6/2.80 ???
Vertauschungen 0 n(logn)1.7/5.34 ???

shellsort(field A, int l, int r) {
  shellsort(A, l, r, 1);
}

shellsort(field A, int l, int r, int step) {
  if (step <= r-l) then {
    shellsort(A, l, r, step*3+1));
    shell(A, l, r, step-1, step);
  }
}

shell(field A, int l, int r, int i, int step) {
  ...
}

insertsort(field A, int l, int r, int step) {
  ...
}

insert(field A, int l, int r, int step) {
  ...
}


Shellsort, Variante 4