Comb Sort Explained

1. Introduction

The comb sort is an algorithm designed by Włodzimierz Dobosiewicz, a Polish computer specialist, at Warsaw University in 1980. It is well-known that bubble sort is one of the worst sorting algorithms having a quadratic running time. Bubble sort can be improved in a way, akin to how shell sort is a variant of insertion sort.

In this tutorial, we’ll learn how the comb sort improves upon bubble sort, aptly known as gapped bubble sort.

2. A Quick Refresher of Bubble Sort

Let’s take a quick gander at the bubble sort algorithm. Bubble sort is a comparison sorting algorithm, where large elements are bubbled (up) to the end of the array. We make several passes of the array. In the th pass, we look at the sub-array . In each pass, we step through the input array element by element, comparing each element to its neighbor, and swapping their values, if .

Consider the following pseudo-code:

If there are no swaps performed in a given iteration, then the array must be sorted, we can safely terminate.

2.1. Rabbits and Turtles

Consider the shuffled array . Let’s run through what the array looks like after each iteration of the outer for-loop of the bubble sort algorithm.

The element is a rabbit and the element is a turtle. Heavier elements that are to be moved towards the end of the array move very quickly, whereas lighter elements that are to be moved to the beginning of the array move by just one step in each iteration.

3. The Comb Sort Algorithm

The bubble sort algorithm operates on neighboring elements of the array. The comb-sort algorithm performs comparison-swap operations on non-contiguous elements. In fact, the key to its speed is that, at the beginning, it compares and swaps, if necessary, elements that are far from each other. Then, it reduces the distance progressively, comparing-swapping nearer elements. That distance is called the gap or increment.

Turtles slow down bubble-sort tremendously. Comb-sort eliminates this problem by performing comparison-swap on distant elements to begin with.

3.1. Vanilla Comb Sort

The vanilla comb-sort algorithm uses increments that form a geometric progression. Let be the number of elements in the array and let be the shrinkage factor. Then, mathematically the gap size takes values from the following sequence:

There are some considerations to the shrinkage factor . As an extreme case, suppose that the array has elements and the shrinkage factor . In such a case, the gap size takes values . -sorting, -sorting and -sorting an array will result in no interaction between the even and odd elements. A large amount of work is left to the point where the gap size equals . In effect, we end up doing a near bubble-sort of array. This is undesirable. The authors have found that the optimal value of the shrinkage factor approximately equals .

3.2. Pseudo-Code

Let’s consider the following pseudo-code:

The outer while-loop iterates as long as at least one of the conditions holds true. Carefully negating this, using De-Morgan’s laws, we find that the while-loop will terminate, when

A sweep of the array with no swaps implicitly means that the array is monotonically increasing, no elements are out of order, and the array is sorted. So, the condition makes intuitive sense.

In each pass, we successively reduce the gap by a factor . If the computed value of the variable at any point is smaller than , we reset it to .

We perform comparison-swap operations on the sub-sequence of elements .

4. The Running Time of Comb Sort

Let’s see how comb sort stacks up, as far as the running time is concerned, as compared with Bubble Sort. The empirical results below show the speedup attained by comb sort vis-a-vis the bubble sort. The worst-case running time of comb sort is .

5. Conclusion

In this article, we learned about how the comb sort algorithm attains a speed-up over bubble sort. To recap, comb-sort eliminates the problem of turtles by comparison-swap operations between far-away elements.