Combsort, Variante 2 (Original)

Hierbei handelt es sich um die Original-Variante. Diese Folge wurde erstmalig von Richard Box und Stephen Lacey vorgestellt (April 1991).

(*) Ich habe keinen plausiblen Grund finden können, warum am Ende die Folge "11, 8, 6, 4, 3, 2, 1" sichergestellt werden muß. Hinsichtlich der Laufzeit bringt das keine großen Vorteile. Ich empfehle daher diesen Teil wegzulassen.

Variante 2.a (iterativ)
Typ Beispiel
Eigenschaften iterativ, in-place, instabil, nicht parallelisierbar
Datenstrukturen Felder
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit Ω(nlogn) Θ(n(logn)1.4) Ο(???)
Vergleiche 2.64*nlogn n(logn)1.4/1.17 ???
Vertauschungen 0 n(logn)1.3/4.57 ???

combsort(field A, int l, int r) {
  gap:= r-l;
  do {
    if (gap > 1) then {
      gap:= Round(Down, gap/1.3);
      if ((gap = 9) or (gap = 10)) then { // (*)
        gap:= 11;                         // (*)
      }                                   // (*)
    }
  } while ((comb(A, l, r, gap)) or (gap > 1));
}

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 2.b (rekursiv)
Typ Beispiel
Eigenschaften rekursiv, in-place, instabil, nicht parallelisierbar
Datenstrukturen Felder
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit Ω(nlogn) Θ(n(logn)1.4) Ο(???)
Vergleiche 2.64*nlogn n(logn)1.4/1.17 ???
Vertauschungen 0 n(logn)1.3/4.57 ???

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

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

combsort(field A, int l, int r, int gap) {
  if (gap < (r-l)) then { 
    combsort(A, l, r, Round(Up, gap*1.3));
    return comb(A, l, r, gap);
  } 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;
  }
}


Combsort, Variante 2