Sorting Algorithms Studies: Bubble Sort

Explanation

This algorithm works by repeatedly comparing the current value with the next value, and swapping them if the next value is lower than the current value; or, if the sorting is being done in decrescent order, if the next value is higher than the current value. Having provided the clarifications, from now on this article will focus on the crescent order implementation.

Some say that the name comes from the fact that, as it happens with the bubbles, that rise to the top in the water, so it happens too to list elements with greater values, which are recurrently pushed to the end (top) of the list.

Structure

It is comprised by two nested loops:

• The outer one loops amongst the numbers that comprise the range between 0 and the size of the array, minus 2. Example: if the array has size 5, the outer loop will loop from 0 to 3. Let’s call the number of the outer loop x.
• The inner loop is the one that actually makes the comparisons and swaps. It loops amongst the numbers that comprise the range between 0 and the length of the array, minus 2, minus the number of the outer loop (x). Example: if the array has size 5, the inner loop will loop from 0 to 3 on the first outer loop, 0 to 2 in the second outer loop, and so on. Let’s call the number of the inner loop y.
• For each y in the inner loop, it compares the element on the index y with the element on the index y + 1. If the first is greater than the second, the elements are swapped.

Also, there is an optimized Bubble Sort implementation. Basically, for each outer loop, a swapped flag is set to False. If there is any swap in an inner loop, swapped is set to True. At the end of the last inner loop, if swapped is False, it means that the array is sorted and no more outer loops are needed, so the outer loop can be ended prematurely and the array can be returned.

Code

This is the implementation of Bubble Sort in Python. It may look slighter more complex than the usual Bubble Sort implementation, but that’s because I’ll to provide codes that work both for the crescent and decrescent sorting.

And this is the implementation of optimized Bubble Sort in Python. Again, this codes works both for the crescent and decrescent sorting.

Finally, here’s the interactive algorithm visualization, with step-by-step execution.

Complexity

Worst-case performance: O(n²)

Best-case performance: O(n²) for the normal implementation; O(n) for the optimized implementation

Average performance: O(n²)

Space complexity ¹: O(n)

Auxiliary space ²: O(1) for the normal implementation; O(2) for the optimized implementation. ³

Benchmark

As the posts from the Sorting Algorithms Studies are posted, I’ll benchmark the algorithms against each other. For now, there’s only Bubble Sort to be shown.

Wrapping Up

Bubble Sort is a simple algorithm, easy to understand and implement. It doesn’t performs well, but it may be enough for some scenarios, like when you have really small lists of when there’s not much time to make a better implementation (like in a hackaton).

Stay tuned for the next chapters of this series!