Combsort, Variante 1 (Grundgerüst)

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

Für dieses Verfahren ist mir keine obere Schranke für die Laufzeit bekannt. Wahrscheinlich läßt er sich jedoch ähnlich Shellsort analysieren, so daß auch ein ähnliches Ergebnis zustande kommt.

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

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

combsort(field A, int l, int r) {
  k:= 0;
  while (h[k] < r-l) do {
    k++;
  }
  do {
    gap:= h[k];
    if (k > 1) then {
      k--;
    }
  } while ((comb(A, l, r, gap)) or (k > 0));
}

boolean comb(field A, int l, int r, int gap) {
  flipped:= false;
  for i:= l to r-gap do {
    if (A[i] > A[i+gap]) then {
      exchange(A[i], A[i+gap]);
      flipped:= true;
    }
  }
  return flipped;
}

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

combsort(field A, int l, int r) {
  if combsort(A, l, r, 0) then {
    ripplesort(A, l, r);
  }
}

ripplesort(field A, int l, int r) {
  if comp(A, l, r, 1) then {
    ripplesort(A, l, r);
  }
}

boolean combsort(field A, int l, int r, int k) {
  if (h[k] < r-l) then { 
    combsort(A, l, r, k+1);
    return comb(A, l, r, h[k]);
  } else {
    return true;
  }
}

boolean comb(field A, int l, int r, int gap) {
  if (l <= r-gap) then {
    if (A[l] > A[l+gap]) then {
      exchange(A[l], A[l+gap]);
      comb(A, l+1, r, gap);
      return true;
    } else {
      return comb(A, l+1, r, gap);
    }
  } else {
    return false;
  }
}