In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
originally designed by Włodzimierz Dobosiewicz in 1980. Later it was rediscovered and popularized by Stephen Lacey and Richard Box with a Byte Magazine article published in April 1991. Comb sort improves on bubble sort
Bubble sort
Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which...
, and rivals algorithms like Quicksort ( visual comparison). 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 one. (Shell sort
Shell sort
Shellsort, also known as Shell sort or Shell's method is an in-place comparison sort. It generalizes an exchanging sort, such as insertion or bubble sort, by allowing the comparison and exchange of elements that lie far apart. Its first version was published by Donald Shell in 1959. The running...
is also based on this idea, but it is a modification of insertion sort
Insertion sort
Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort...
rather than bubble sort.)
The gap starts out as the length of the list being sorted divided by the shrink factor (generally 1.3; see below), and the list is sorted with that value (rounded down to an integer if needed) for the 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.
Shrink factor
The shrink factor has a great effect on the efficiency of comb sort. In the original article, the authors suggested 1.3 after trying some random lists and finding it to be generally the most effective. A value too small slows the algorithm down because more comparisons must be made, whereas a value too large means that no comparisons will be made.
Text describes an improvement to comb sort using the base value as the shrink factor. It also contains a pseudocode implementation with a pre-defined gap table.
Combsort11
With a shrink factor around 1.3, there are only three possible ways for the list of gaps to end: (9, 6, 4, 3, 2, 1), (10, 7, 5, 3, 2, 1), or (11, 8, 6, 4, 3, 2, 1). Experiment shows that significant speed improvements can be made if the gap is set to 11 whenever it would otherwise become 9 or 10. This variation is called Combsort11.
If either of the sequences beginning with 9 or 10 were used, the final pass with a gap of 1 is less likely to completely sort the data, necessitating another pass with a gap of 1. The data is sorted when no swaps were done during a pass with gap = 1.
It is also possible to use a predefined table, to choose which gaps to use every pass.
Combsort with different end
Like many other sort efficient algorithms (like quick sort or merge sort
Merge sort
Merge sort is an O comparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output. It is a divide and conquer algorithm...
), combsort is more effective in its earlier passes than it is during the final passes, when it resembles a bubble sort
Bubble sort
Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which...
. Combsort can be made more effective if the sorting method is changed once the gaps reach numbers small enough. For example, once the gap reaches a size of about 10 or smaller, stopping the combsort and doing a simple gnome sort
Gnome sort
Gnome sort, originally proposed by Hamid Sarbazi-Azad in 2000 and called , and then later on described by Dick Grune and named "Gnome sort", is a sorting algorithm which is similar to insertion sort, except that moving an element to its proper place is accomplished by a series of swaps, as in...
Cocktail sort, also known as bidirectional bubble sort, cocktail shaker sort, shaker sort , ripple sort, shuffle sort, shuttle sort or happy hour sort, is a variation of bubble sort that is both a stable sorting algorithm and a comparison sort...
Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort...
, will increase the sort's overall efficiency.
Another advantage of this method is that there is no need to keep track of swaps during the sort passes to know if the sort should stop or not.
Pseudocode
function combsort(array input)
gap := input.size //initialize gap size
loop until gap = 1 and swaps = 0 //update the gap value for a next comb. Below is an example
gap := int(gap / 1.247330950103979) if gap < 1 //minimum gap is 1
gap := 1 end if
i := 0
swaps := 0 //see bubblesort for an explanation
//a single "comb" over the input list loop until i + gap >= input.size //see shellsort for similar idea if input[i] > input[i+gap] swap
Swap (computer science)
In computer programming, the act of swapping two variables refers to mutually exchanging the values of the variables. Usually, this is done with the data in memory...
(input[i], input[i+gap])
swaps := 1 // Flag a swap has occurred, so the // list is not guaranteed sorted end if
i := i + 1 end loop
Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which...
, a generally slower algorithm, is the basis of comb sort.
Cocktail sort, also known as bidirectional bubble sort, cocktail shaker sort, shaker sort , ripple sort, shuffle sort, shuttle sort or happy hour sort, is a variation of bubble sort that is both a stable sorting algorithm and a comparison sort...
, or bidirectional bubble sort, is a variation of bubble sort that also addresses the problem of turtles, albeit less effectively.
as the shrink factor. It also contains a pseudocode implementation with a pre-defined gap table.