Comb Sort

Comb sort is a relatively simple sorting algorithm originally designed by Włodzimierz Dobosiewicz and Artur Borowy in 1980, later rediscovered (and given the name "Combsort") by Stephen Lacey and Richard Box in 1991. Comb sort improves on bubble sort in the same way that Shellsort improves on insertion sort.

'' nist.govs "diminishing increment sort" definition mentions the term 'comb sort' as visualizing iterative passes of the data, "where the teeth of a comb touch;" the former term is linked to Don Knuth.

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 the gap between swapped elements goes down (for each iteration of outer loop) in steps of a "shrink factor" ''k'': .

The gap starts out as the length of the list ''n'' being sorted divided by the shrink factor ''k'' (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. ''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 1 gap size.

The pattern of repeated sorting passes with decreasing gaps is similar to Shellsort, but in Shellsort the array is sorted completely each pass before going on to the next-smallest gap. Comb sort's passes do not completely sort the elements. This is the reason that Shellsort gap sequences have a larger optimal shrink factor of about 2.2.

Pseudocode

function combsort(array input) is

gap := input.size // Initialize gap size
shrink := 1.3 // Set the gap shrink factor
sorted := false

loop while sorted = false
// Update the gap value for a next comb
gap := floor(gap / shrink)
if gap ≤ 1 then
gap := 1
sorted := true // If there are no swaps this pass, we are done
end if

// A single "comb" over the input list
i := 0
loop while i + gap < input.size // See Shell sort for a similar idea
if input > input +gapthen
swap(input input +gap
sorted := false
// If this assignment never happens within the loop,
// then there have been no swaps and the list is sorted.
end if

i := i + 1
end loop
end loop
end function

Python code

Plus, two quick Python implementations: one works on the list (or array, or other mutable type where the operations used on it make sense to the language) in-place, the other makes a list with the same values as the given data and returns that after sorting it (similar to the builtin `sorted` function).

from math import floor

def combsort_inplace(data):
length = len(data)
shrink = 1.3
gap = length
sorted = False
while not sorted:
gap = floor(gap / shrink)
if gap <= 1:
sorted = True
gap = 1
# equivalent to `i = 0; while (i + gap) < length: ...... i += 1`
for i in range(length - gap):
sm = gap + i
if data > data m
# because Python is very nice, this accomplishes the swap
data data m= data m data sorted = False

def combsort(data):
length = len(data)
shrink = 1.3
gap = length
out = list(data)
is_sorted = False
while not is_sorted:
gap = floor(gap / shrink)
if gap <= 1:
is_sorted = True
gap = 1
for i in range(length - gap):
sm = gap + i
if out > out m
out out m= out m out is_sorted = False
return out

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.

References

{{DEFAULTSORT:Comb Sort
Sorting algorithms
Comparison sorts
Articles with example pseudocode