Bubble sort is one of the first sorting algorithms presented in Computer Science. It's not a very practical sorting algorithm, but it is useful for presenting the concepts of sorting and teaching computer science students to think algorithmically.
If you investigate bubble sort further, you will learn that there have been attempts to improve upon the efficiency of bubble sort. One such algorithm is comb sort. Comb sort attempts to improve bubble sort by eliminating turtles, which are small numbers at the end of the list you're sorting. Turtles cause bubble sort to run slowly, because they require many swaps as they slowly move 1 position at a time with each and every pass of bubble sort.
Comb Sort Gaps and Shrink Factor
Bubble sort always compares adjacent values while sorting, which causes turtles to only move 1 position at a time to the front. Comb sort attempts to improve the efficiency of bubble sort by comparing values farther apart. This allows smaller numbers at the end of the list to move several positions forward in a single pass, greatly reducing the overall number of swaps. Comb sort refers to these larger distances as gaps, and uses a shrink factor, typically 1.3, to calculate the optimum values for these gaps. As comb sort continues to sort the list, the gaps get smaller and smaller until the gap is 1. With a gap of 1, comb sort is essentially doing a bubble sort.
For example, if you have a list of 10 integers to sort using comb sort, the initial gap is the length of the list divided by the shrink factor.
gap = 10 / 1.3 = 7
Therefore for the first set of exchanges you will be comparing values 7 positions away from each other.
6 0 9 3 7 5 4 1 8 2
In the list above, you will first compare 6 with 1. Because 1 is less than 6, an exchange will happen and the number 1 ( a turtle ) will quickly move to the front of the list, eliminating many swaps that would have occurred with bubble sort.
1 0 9 3 7 5 4 6 8 2
You will continue to compare 0 with 8 and 9 with 2 in the list above. Since the number 2 is less than 9, it will quickly jump to the front of the list as well.
Once you complete all comparisons using a gap of 7, you make the comparisons again using new gaps calculated in a similar manner.
gap = 7 / 1.3 = 5
gap = 5 / 1.3 = 3
gap = 3 / 1.3 = 2
gap = 2 / 1.3 = 1 <- bubble sort
Eventually comb sort uses a gap of 1, which is bubble sort.
Comb Sort in Python
Here is an implementation of comb sort in Python using a shrink factor of 1.3.
def comb_sort(lst): """ Performs in-place sort using Comb Sort. :param lst: list of integers :return: None >>> lst = [6, 0, 9, 3, 7, 5, 4, 1, 8, 2] >>> comb_sort(lst) >>> assert(lst == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) """ if lst is None or len(lst) < 2: return gap = len(lst) swap_occurred = True while gap > 1 or swap_occurred: gap = int(gap / 1.3) if gap < 1: gap = 1 i = 0 swap_occurred = False while i + gap < len(lst): if lst[i] > lst[i + gap]: lst[i], lst[i+gap] = lst[i+gap], lst[i] swap_occurred = True i += 1
As you can see, comb sort is very easy to implement in Python. Using a list of 10 unsorted integers as shown in the doctest, comb sort will perform comparisons using gaps of 7, 5, 3, 2, and 1. When the gap is 1, comb sort is performing a bubble sort. As with bubble sort, comb sort will continue to compare adjacent values until a pass has successfully completed with no swaps, which means the list is sorted.
Hopefully you appreciate bubble sort more than before as well as understand that turtles, small values at the end of the unsorted list, make it slow. Comb sort improves upon bubble sort by comparing values at farther distances to eliminate turtles.
Comb sort isn't the only sorting algorithm that attempts to improve bubble sort by eliminating turtles. I presented another algorithm, called cocktail sort, that also tries to eliminate turtles to improve bubble sort.
Posted by David Hayden