Shellsort, Variante 1 (Grundgerüst)

Hierbei handelt es sich um das Grundgerüst aller Varianten.

h[0..m] muß eine Folge von ganzen Zahlen sein, für die gilt: 1 = h[0] < h[1] < ... < h[k] ...

Es gibt viele verschiedene Folgen. Diese alle aufzuzählen würde den Rahmen dieser Seite sprengen. Ich stelle daher nur die wichtigsten vor. Da eine Laufzeitanalyse sehr schwierig ist, kann man davon ausgehen, daß die beste Folge noch nicht gefunden wurde.

Statt Insertsort kann als "internes Sortierverfahren" auch Bubblesort (mit vorzeitigem Abbruch) verwendet werden. Allerdings ist die Laufzeit dann etwas schlechter.

Variante 1.a (iterativ)
Typ standard
Eigenschaften iterativ, in-place, instabil, parallelisierbar
Datenstrukturen Felder
Speicher Ω(m) Θ(m) Ο(m)
Laufzeit Ω(n) Θ(???) Ο(???)
Vergleiche ??? ??? ???
Vertauschungen 0 ??? ???

shellsort(field A, int l, int r) {
  k:= 0;
  while (h[k] <= r-l) do {
    k++;
  }
  do { 
    step:= h[k];
    k--;
    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) {
  for i:= "l+step" to "r" step "step" do {
    j:= i;
    while ((j > l) and (A[j-step] > A[j])) do {
      exchange(A[j-step], A[j]);
      j:= j - step;
    }
  }
}

Variante 1.b (rekursiv)
Typ standard
Eigenschaften rekursiv, in-place, instabil, parallelisierbar
Datenstrukturen Felder
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit Ω(n) Θ(???) Ο(???)
Vergleiche ??? ??? ???
Vertauschungen 0 ??? ???

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

shellsort(field A, int l, int r, int k) {
  if (h[k] <= r-l) then {
    shellsort(A, l, r, k+1);
    shell(A, l, r, h[k]-1, h[k]);
  }
}

shell(field A, int l, int r, int i, int step) {
  if (i >= 0) then {
    do parallel {
      shell(A, l, r, i-1, step);
    } and {
      insertsort(A, l, r-i, step);
    }
  }
}

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

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