In computer science, comb sort is a relatively simplistic sort algorithm designed by Stephen Lacey and Richard Box, who described it in Byte Magazine in April 1991. Comb sort improves on bubble sort and rivals in speed more complex algorithms like Quicksort. 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.) Computer science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... The front cover of the April 1981 issue of BYTE (Vol 6. ... 1991 (MCMXCI) was a common year starting on Tuesday of the Gregorian calendar. ... Bubble sort, also known as exchange sort, is a simple sorting algorithm. ... Quicksort in action on a list of random numbers. ...

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 is also based on this idea, but it is a modification of insertion sort rather than bubble sort.) Shell sort is a sorting algorithm that requires fewer than O(n²) comparisons and exchanges, on average. ... Insertion sort is a simple sort algorithm in which the sorted array (or list) is built one entry at a time. ...

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 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 performs the final sort in the same manner. The final 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 may not kill enough turtles to be practical.

Text [1] 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). Only the last of those endings kills all turtles before the gap becomes 1. Therefore, 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.

Implementations

Python

 def update_gap(gap): gap = (gap * 10) / 13 if gap == 9 or gap == 10: gap = 11 return max(1, gap) def combsort(x): gap = len(x) swapped = True while gap > 1 or swapped: gap = update_gap(gap) swapped = False for i in range(0, len(x) - gap, gap): if x[e] > x[e + gap]: x[e], x[e + gap] = x[e + gap], x[e] swapped = True 

Python is an interpreted, interactive programming language created by Guido van Rossum in 1990, originally as a scripting language for Amoeba OS capable of making system calls. ...

Java

 private static int newGap(int gap) { gap=gap*10/13; if(gap==9||gap==10) gap=11; return gap; } private static void sort(int a[]) { int gap=(int)(a.length*10/13); int temp; for(;gap>=1;) { for(int i=0;i<=a.length-gap;i++) { if(a[i]>a[i+gap-1]) { temp=a[i]; a[i]=a[i+gap-1]; a[i+gap-1]=temp; } } gap=newGap(gap); } } 

Java is an object-oriented programming language developed by James Gosling and colleagues at Sun Microsystems in the early 1990s. ...

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.