Comb Sort – An extension over the Bubble Sort

Introduction

This article is in continuation of the article Improving Bubble Sort – A detailed explanation which I wrote to explain the basic idea behind bubble sort.

Purpose of the article

This is an improvement over Bubble Sort, an improvement which is pretty much similar to Shell Sort over Insertion Sort. To know more about the relationship between Shell Sort and Insertion Sort, please read the articles in my previous posts.

What are we trying to improve?

Before we try to improve, we must know what to improve. The thing which is clear is that Bubble sort takes more time (or may I say more comparisons to do sorting, almost N * [N+1]/2 ). Somehow if we can minimize this number our job is done.

How to do this?

Well, we need to closely look into the bubble sort procedure.

What happens if the array contains elements where all the smaller elements are to the left and all the larger elements are to the right and we are trying to sort the array in ascending order?

In this case bubble sort may perform better, with lesser number of movements/swapping. Now assume the reverse scenario, where the bigger numbers are in the beginning and the smaller numbers are at the end. The movement of numbers from one end to the other takes a lot of time. One iteration of the outer loop will shift all the element by one position to the left/right.

Now consider the scenarios where the whole array is sorted except for the smallest number which is at the tenth location (extreme right), then it will definitely take ten iterations of the outer loop to shift it to the beginning.

In such a situation even a sorted array takes 10 * 9 / 2 = 45 comparisons. Now that we have identified the problem, we can talk about fixing it.

Comb Sort – an improvement over Bubble Sort

In the world of algorithms, randomness plays a very important role. In the scenario above, what if we would have swapped two random elements instead of swapping the adjacent elements? Would it have improved? The answer is may be or may not be. We might have ended up swapping the sorted elements throwing them at the wrong positions repeatedly.

So let me re-frame my sentence, ” In the world of algorithms, organised randomness plays a very important role”. In the whole article I will just try to prove this statement and we hope to reach at an agreement and hence write an algorithm which proves to be worthy of the debate. “The Comb Sort”.

Idea behind Comb Sort

This is similar to the Bubble Sort, “Compare and Swap”. Only difference here is, compare distant elements instead of the adjacent ones.

But how do we decide which distant elements to compare?

The answer to this would be Organized Randomness. So, in the beginning of the algorithm we have to decide the distance between the elements whom we need to compare, secondly we also need to make sure that after each iteration the distance must converge to swap elements which are nearer than the elements we compared in the previous iteration. This will ensure that we don’t do any out of order swapping and kill the purpose of organised randomness.

Comb Sort – Explanation

We define a gap variable which will help in deciding the distanc between the elements to be compared. This gap should descrease by a certain factor after each iteration of the outer loop to facilitate a healthy and non-repetitive comparison and swap.

For e.g.: If we swap two elements at a distance 8 in first iteration, then we must swap two elements at a distance lesser than 8 (need not be 7, it can be 6 or 5 or any other number) in the second iteration. This procedure is called shrinking and the factor by which gap shrinks each tiime is called the shrinking factor.

After a lot of mathematical calculations and derivations, it has been established to 1.3 for best results. You are free to choose your shrinking factor. In some implementations where the list to be sorted is small, instead of evaluatiing and finding the gap in each iteration we try to hard code it. The shrink factor list would be
[11, 8, 6, 4, 3, 2, 1]

Do not worry if most of the things above didn’t make much sense. We will try to demonstrate the same using some diagrams.

Demonstration

To start with we have the following array:

4 6 2 3 7 1 8 0 9 5

We choose to use the above mentioned shrink factors, to start with we will choose anything which is less than the size of the array to sort, hence let us select 8 as 8 is less than 10.

Now we start the first iteration, where we do the following comparisons:

Iteration 1:

Gap : 8

step1

Please notice that had it been the case of bubble sort, it would have taken 8 iterations to get 5 at index 1.
We use the resultant array from iteration 1 as input for the next iteration.

Iteration 2:
Now we shrink the gap by picking another gap from the shrink factor array. We could have dynamically found the gap by dividing it with 1.3 as mentioned above, but it doesn’t actually matter.
Gap : 6

step2

Iteration 3:
We use the resultant array from iteration 2 as input for the next iteration. Now we shrink the gap by picking another gap from the shrink factor array.
Gap : 4
step3

Iteration 4:
We use the resultant array from iteration 3 as input for the next iteration. Now we shrink the gap by picking another gap from the shrink factor array.
Gap : 3

step4

Iteration 5:
We use the resultant array from iteration 4 as input for the next iteration. Now we shrink the gap by picking another gap from the shrink factor array.
Gap : 2

step5

Iteration 6:
We use the resultant array from iteration 5 as input for the next iteration. Now we shrink the gap by picking another gap from the shrink factor array.
Gap : 1

step6

Iteration 7:
We use the resultant array from iteration 5 as input for the next iteration. Now the gap can’t reduce to less than 1 so use gap = 1 for one more time.
Gap : 1

step7

Analysis

This time we are not going to analyze it in deep, we will just try to find out the total number of swapping and comparisons involved in the sorting of this array.
Comparisons would be total number of rows in all the images above and swapping will be the count of all the statements which say “we find the elements out of order and we swap both of them.”

Comparisons = 45
Swaps = 12

Code and Implementation

Conclusion

So this is how we can improve Bubble Sort, its worth mentioning that the name changes to Comb Sort. If compared all the three ways of Sorting, below is the result:

Plain Bubble Sort : Comparison – 72 , Swap – 20
Optimized Bubble Sort : Comparison – 44 , Swap – 20
Comb Sort : Comparison – 45 , Swap – 12

This proves that organized randomness helps and we can employ Comb Sort in place of bubble sort to get things faster.

To know more about Comb Sort please visit the wiki for Comb Sort
Stay connected and stay Subscribed