Bubble Sort Primer

What is the sorting problem?

We are given an array of elements, e.g., numbers, and we desire to put them in order, either increasing or decreasing order. Sorting is important in many areas. For instance, Google is ranking webpages according to their suitability for your query and then sorting them so that the webpage with the highest relevance is presented first. As a second example, Google Maps sorts routes to your destination by distance and presenting them in order of shortest-to-longest or fastest-to-slowest.

How does bubble sort work?

Bubble sort is one of the simplest sorting algorithms to understand and implement. It is often the first sorting algorithm taught in an algorithms course. The way bubble sort works is to compare every successive pair of elements in an array and swapping them if they are not in the right order. This process is continued over and over again till the full array is sorted. It is called bubble sort because the largest element “bubbles” to its correct, intended, location, followed by the bubbling of the second largest element to its location and so on.

Below is a simple illustration of how bubble sort works. We are given the array [35, 67, 12, 95, 21] and desire to sort it in increasing order, so that 12 becomes the first element and 95 becomes the last element. In other words, the array should become [12, 21, 35, 67, 95]. We will show how bubble sort works by showing the first few steps.

To begin with, bubble sort compares every adjacent pair of elements beginning from the left. So, it first compares 35 and 67. They are already in order, so nothing needs to be done. Then it compares 67 and 12. They are NOT in order. So bubble sort swaps them so that the array becomes [35, 12, 67, 95, 21], as shown above in the second step.

Bubble sort continues its inspection. 67 and 95 are already in order so no swapping needs to be done. Finally, 95 and 21 are compared and found to be in an incorrect order, so they are swapped. So after one full sweep of the array (the position before the green line above), bubble sort has arrived at [35, 12, 67, 21, 95].

Note that after one full sweep bubble sort has made the largest element to be the final element in the array. Now it continues to make another sweep again from the left.

You notice that 35 and 12 need to be swapped, and so on. You proceed further down the array. If you are coding this, for the second sweep, you only have to compare till the last-but-one element because the last element is already in its intended location. Similarly, for the third sweep, you can stop at the last-but-two element, and so on.

How efficient is bubble sort?

Bubble sort is not the most efficient sorting algorithm. In fact, it is among the most inefficient sorting algorithms. When computer scientists talk about efficiency, they imagine the worst scenario possible and assess the operation of the algorithm.

The reason for bubble sort's inefficiency is because an element will have to go through multiple swaps before it arrives at its rightful location (as opposed to a direct swap to its final location). At the same time, this inefficiency means that once the element “settles” down, we know that it has reached its location and thus bubble sort “knows” when the array gets sorted and thus the swapping operations can stop.

Formally, in computer science terminology, bubble sort is considered to have O(n^2) worst case time complexity, meaning as the size of the array increases the time taken to sort it increases not linearly, but quadratically.

What are the advantages of bubble sort?

As inefficient as bubble sort is, it does come with some advantages. First, it is easy to understand, and thus is often the first sorting algorithm students are exposed to.

Second, bubble sort belongs to the family of “comparison sorting” algorithms, meaning algorithms that do sorting by only performing comparisons.

Third, bubble sort has the property of “sorting in place”, meaning it doesn’t need to create a copy of the array since at any point in time it is only comparing two elements with each other.

Fourth, bubble sort also is among the sorting algorithms that knows “when it is done”, i.e., when it can stop making comparisons. If you give an already sorted array to bubble sort, e.g., [20, 34, 56, 78, 100] by the end of the first sweep bubble sort will know that no swaps happened and thus the array is already sorted and thus it can stop.

Finally, bubble sort is part of a family of “stable sorting” algorithms. This means if the algorithm encounters two equal valued elements, their relative positions do not change over the course of the algorithm's operation.

How can we code bubblesort in Python?

Here is a sample implementation of a bubblesort function in Python.

Note that we are giving an "array" as input to the bubblesort function. There are two nested for loops and the ranges of the for loops are carefully controlled so as to not make any needless comparisons.

We also have a boolean variable called "is_swapped" that is checked in every sweep and if no swaps have occurred the function returns without completing any remaining outer loops. Also note that we are using Python notation to do swapping in place without an intermediate variable. We are also keeping track of the number of comparisons and swaps for later analysis.

Finally, note Python's call-by-object-reference style that updates the array when passed into the function.

We can invoke this function as follows:

The output is:

What happens if we give it an alredy sorted list, such as [10,29,30,45,50,89]?

Note that the algorithm exits after one sweep because it recognizes that there have been no swaps and thus the array must be sorted.

In this blogpost we have learnt about the bubble sort algorithm and how to code it in Python. Learn about a different sorting algorithm in this blog post about insertion sort. Also learn about Python's enumerate() functionality.

If you liked bubblesort, learn about how to implement bubblesort in Javascript as an instance of nested for loops.

Want to learn Python with us? Sign up for 1:1 or small group classes.