Shellsort, Variante 2 (Shell)

Hierbei handelt es sich um eine Beispielfolge. Die Folge von D.L. Shell (1959) "1,2,4,8,16,32,64,128,256,...,x" verspricht eine Laufzeit, die in Ω(nlogn) und Ο(n²) liegt. Jede Zahl ist eine Zweierpotenz. (xp+1 = 2*xp = 2p+1, x <= (r-l+1)/2). Diese Folge ist sehr ungünstig und sollte nicht angewendet werden. Die empirische Laufzeit wurde bei einer 2er-Potenz-Feldgröße ermittelt und stellt somit den ungünstigsten Fall dar.

Variante 2.a (iterativ)
Typ Beispiel
Eigenschaften iterativ, in-place, instabil, parallelisierbar
Datenstrukturen Felder
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit (p) Ω(n) Θ(???) Ο(???)
Laufzeit Ω(nlogn) Θ(n(logn)4) Ο(n²)
Vergleiche nlogn n(logn)3.0/35 ???
Vertauschungen 0 n(logn)3.8/326 ???

shellsort(field A, int l, int r) {
  step:= r-l+1;
  do {
    step:= Round(Up, step/2);
    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 2.b (rekursiv)
Typ Beispiel
Eigenschaften rekursiv, in-place, instabil, parallelisierbar
Datenstrukturen Felder
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit (p) Ω(n) Θ(???) Ο(???)
Laufzeit Ω(nlogn) Θ(n(logn)4) Ο(n²)
Vergleiche nlogn n(logn)3.0/35 ???
Vertauschungen 0 n(logn)3.8/326 ???

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+1) div 2) then {
    shellsort(A, l, r, step*2));
    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 2