Improving Bubble Sort – A detailed explanation

Introduction

Ever wondered why bubble sort is slow? Does it look similar to Insertion Sort ? Can it be improved to have better than quadratic time in average cases?
Here we start with a detailed analysis of bubble sort in the easiest possible way. Bubble Sort as the name suggests, bubbles up the heaviest (or may be lightest, depending on the comparison operator) elements to the top.

Purpose of the article

The article Improving Bubble Sort, is dedicated to explain the mechanism behind bubble sort in detail, apart from that, it also offers an improved bubble sort. Moreover, it also helps us understand other improvements which can be applied to make it better. It ends with the mention of Comb Sort which is an improved version of Bubble Sort.

Bubble Sort – The basic approach

I always love to write about the bubble sort, it’s one of the easiest algorithms to understand (if no optimization done). No one can ever make a mistake coding this. And the best part is, it involves no tricks, just a simple thumb rule, “Compare and Swap”.

So as far as you have the information about how to compare you are good to go. Let us see how, this simple idea of comparing and swapping the adjacent elements leads to self organizing an array to produce a sorted array.

Idea behind bubble sort

I would like to show u the approach diagrammatically and then explain the magic behind it. To start with lets assume that we have the following array. We will also note the indices of all the elements to ease our understanding. The array has the elements randomly distributed, which is an average use case.

Indices – 0—1—2—3—4—5—6—7—8—9
Array – 4—6—2—3—7—1—8—0—9—5

We will iterate through the array and compare the adjacent elements, if the element to the left is greater than the element to the right, we make a swap and continue doing the same till we reach the end of the array.

To achieve this we will maintain a pointer j which will travel one step at a time to the right, and facilitate the comparison and swapping. So the code would be something like this below:

Now this will complete one iteration. And if applied on the above array, it will produce a result shown below for each value of j

step1

If we see the above result, it is pretty clear that at the end of the iteration the array is not sorted. That is absolutely correct, because we just did one iteration and if bubble sort can sort the array in one iteration then it would be considered as the best sorting technique in the world, which performs in linear time and that too with an in-place sorting mechanism.

By looking at the result of the iteration above, we can be sure of one thing, ‘at the end of one iteration the biggest element is at the end of the array’. That precisely means that bubble sort results in sorting the array from the back.

A simple calculation would show that if one iteration is needed to arrange one item at it’s right place then we need N or N-1 iterations to arrange all the items at their respective places.
The thing which is obvious is that we need more iterations, something like below:

The above code shows that we need another loop to do N iterations so that all the N elements are placed at the right positions.

Analysis

Now as we see the above code, we can easily deduce that the first loop runs N time and the inner loop runs for N-1 times for each iteration of the first loop. Hence total number of times our comparison code is executed sums down to N(N-1) times. This is effectively equivalent to quadratic running time, similar to most of the quadratic running time algorithms like (Insertion Sort, Shell Sort, Selection Sort etc).

Let me write down the state of the array for each value of i and j, then we will try to optimize the sort to reduce the time taken.

Following is the input array which needs a sorting.

4 6 2 3 7 1 8 0 9 5

For the value of i equal to zero the inner loop runs till the end of the array. We color the numbers which were swapped for a particular value of j. We also maintain if any swapping happened for a given value of j

step2

The output of the first iteration is considered to be the input of the next iteration. Hence, the below state is for i = 1

step3

The output of the second iteration is considered to be the input of the next iteration. Hence, the below state is for i = 2

step4

and so on for different values of i and j.

step5

step6

step7

step8

step9

There would be two more iterations for i = 8 and i = 9, but the state of the array will not change, thats why I am not putting two more images similar to the above one.

Two things worth noticing from the above demonstration:
1) We don’t need steps where i is greater than 7. I can also put it in another way, we don’t need steps when the previous step has not registered any swaps.
2) We don’t need to traverse the inner loop till the end in all the iterations, because bubble sort guarantees that the elements at the end are sorted one by one from the right. That precisely means when i = 3 then at least three elements from the end are at their correct positions. So, we can run the inner loop for N-i times.

Lets talk about the running time in terms of number of comparisons and swapping. Each row in all the above diagrams will add one comparison, so total number of comparisons would be 9 times for each value of i. Which is equal to 9 * 10 = 90.

And we can count the swaps by scanning our images, it adds up to 20.

Improvements

1)

If we can keep a track of the fact that if no swaps are done in a given iteration then we don’e need the next iteration. So basically we do not need the comparisons for iterations i = 8 and i = 9.
Total comparisons in this case would be 9 * (10-2) = 72 and swaps remain same as 20.

2)

If we can utilize the fact that we do not need to traverse the array till the end in the inner loop we can get rid of many comparisons as follow:

step3_2

step4_2

step5_2

step6_2

step7_2

step8_2

step9_2

The total number of comparisons reduces equals to the number of rows, which sums up to 44. The number of swaps remain same as 20.

Code and Implementation

Conclusion

Hence, we can improve the plain bubble sort to make half comparisons than it used to do in the traditional approach.
Basically, not a better improvement but still instead of N * N , now it is N (N+1) / 2, which clearly is reduced to half. Still the order remains quadratic. This can be further improved

How to improve it further?
There is an improvemnet over the bubble sort, which is called Comb Sort. We will be looking into Comb Sort in the next article.
For any other details please visit the Wiki for Bubble Sort

Hope this help, happy learning. Feel free to write comments and ask questions.
Stay connected and stay Subscribed