Traces by Comb Sort on random sequences {100}

Swaps by Comb Sort on random sequences {100}

Traces by Comb Sort on reversed sequence {100} (worst case)

Swaps by Comb Sort on reversed sequence {100} (worst case)

Comb sort (or Dobosiewicz Sort) is similar to bubble sort in that is iterates through the sequence multiple times, swapping elements that are not ordered as it goes. The difference is that comb sort does not start off looking at adjacent elements but instead looks at elements with a certain distance, called the gap. This gap progressively shifts down as the algorithm continues.

Similar to cocktail sort, comb sort improves upon bubble sort due to its ability to deal with the “turtles problem” (small elements near the end of the list slowing down the algorithm).
However it still retains the same worst case computational complexity.

One interesting thing to note however, is that Comb sort is almost as fast as a Quick Sort!

The gap is first equal to n, and after each iteration is reduced by a shrink factor (k) until it reaches the value of 1. Hence, at the very end, the Comb Sort behaves precisely like the Bubble Sort.

The shrink factor has a significant effect on the efficiency of comb sort. k = 1.3 has been suggested as an ideal shrink factor by the authors of the original article after empirical testing on over 200,000 random lists. A value too small slows the algorithm down by making unnecessarily many comparisons, whereas a value too large fails to effectively deal with turtles, making it require many passes with gap size of one.

Steps

• 1. Set gap = n
• 2. While there is swap needed:
• 2.a. Shrink the gap by k such that gap always >= 1.
• 2.b. Compare each pair of elements separated by the gap and if they are in reversed order, swap them.
• 2.c. If gap = 1 and no swap made, then stop: we are done.

Code

void CombSort (Iterator begin, Iterator end)
{
  auto distance = distance(begin, end);
  if (distance < 2)
    return;

  auto gap = distance;
  bool hasSwapped = true;
  while (hasSwapped)
  {
    hasSwapped = false;

    // Compute new gap
    gap /= 1.3;
    if (gap > 1)
      hasSwapped = true;
    else
      gap = 1;

    for (auto it = begin; it + gap < end; ++it)
      if (Compare(it, (it + gap)))
      {
        swap(it, (it + gap));
        hasSwapped = true;
      }
  }
}

Comb sort starts the swapping form the beginning with a gap of n/1.3.
Therefore, it may swap ~ n - n/1.3 elements.

It then loop again starting from the beginning with a new gap of n/1.3²

Further illustration of the previous descriptions.

At the end, the gap is equal to 1 (with at least 1 run) and behave like bubble sort to finish the process.

Useful maths, Asymptotics of the generalized harmonic number H_n,r:

$$H_{n,r} = \sum_{k=1}^{n} \frac{1}{k^r}$$ For $$n \approx 1$$ $$H_{n,1} \in O(log(n))$$

Time

Best

The best configuration occurs when all elements are already sorted or nearly sorted.
In that case, the loop with gap=1 will be run only once (as the others); let us read its sequences from the end of computation for a more convenient formulation:

Average / Worst

The average and worst case runtime of Comb sort (or Dobosiewicz sort) are O(n²). Proving this is a bit tricky, but has been proved using a method based on Kolmogorov complexity (e.g. Survey by Vitanyi, page 16).

Space

Comb Sort does not use any buffer nor does make any recursion. Thus, it requires O(1) space in all case.