Comb sort

Comb sort

Class	Sorting algorithm
Data structure	Array
Worst-case performance	$O(n^{2})$
Best-case performance	$\Theta (n\log n)$
Average performance	$\Omega (n^{2}/2^{p})$, where p is the number of increments
Worst-case space complexity	$O(1)$

Comb sort is a relatively simple sorting algorithm originally designed by Włodzimierz Dobosiewicz in 1980. Later it was rediscovered by Stephen Lacey and Richard Box in 1991. Comb sort improves on bubble sort.

Algorithm

The basic idea is to eliminate turtles, or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. Rabbits, large values around the beginning of the list, do not pose a problem in bubble sort.

In bubble sort, when any two elements are compared, they always have a gap (distance from each other) of 1. The basic idea of comb sort is that the gap can be much more than 1. The inner loop of bubble sort, which does the actual swap, is modified such that gap between swapped elements goes down (for each iteration of outer loop) in steps of shrink factor: [ input size / shrink factor, input size / shrink factor^2, input size / shrink factor^3, ..., 1 ].

The gap starts out as the length of the list being sorted divided by the shrink factor (generally 1.3; see below) and one pass of the aforementioned modified bubble sort is applied with that gap. Then the gap is divided by the shrink factor again, the list is sorted with this new gap, and the process repeats until the gap is 1. At this point, comb sort continues using a gap of 1 until the list is fully sorted. The final stage of the sort is thus equivalent to a bubble sort, but by this time most turtles have been dealt with, so a bubble sort will be efficient.

The shrink factor has a great effect on the efficiency of comb sort. 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.

Pseudocode

 function combsort(array input)

    gap := input.size // Initialize gap size
    shrink := 1.3 // Set the gap shrink factor
    sorted := true // Set a flag to keep the sort going if the
                   // first few passes fail to sort any items.

    loop until gap = 1 and ( swapped = false or sorted = false )
        // Update the gap value for a next comb
        gap := int(gap / shrink)
        if gap < 1
          // Minimum gap is 1
          gap := 1
        end if
        

        i := 0
        swapped := false // See bubble sort for an explanation
        

        // A single "comb" over the input list
        loop until i + gap >= input.size // See Shell sort for similar idea
            if input[i] > input[i+gap]
                swap(input[i], input[i+gap])
                swapped := true // Flag a swap has occurred, so the
                                // list is not guaranteed sorted
                sorted := false // A swap occurred; end sorting if no
                                // more swaps occur.
             end if
 
             i := i + 1
         end loop
         

     end loop
 end function

See also

• Bubble sort, a generally slower algorithm, is the basis of comb sort.
• Cocktail sort, or bidirectional bubble sort, is a variation of bubble sort that also addresses the problem of turtles, albeit less effectively.