Sorting Algorithms Studies: Bubble Sort

Lately, I decided to revise on some subjects that I studied a long time ago. One of these subjects is sorting algorithms. And, by studying it, I thought that creating a material explaining these algorithms could be helpful. Yeah, it’s one more person talking about this, but different people have different visions, and looking through other perspectives is always a good thing.

The first article on this subject will be about the first sorting algorithm that people learn, usually: 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.

Step By Step Execution

The execution below will illustrate the steps of a crescent ordering bubble sort (without optimizations) execution.

The input data is:

a = [3, 1, 5, 4, 2]
a_size = 5

Array - Initial

Array - Initial. Image extracted from https://algorithm-visualizer.org/

The outer loop will define the x range. From the input data, we can assume that x will range from 0 to (a_size - 2) => 0 to (5 - 2) => 0 to 3.

With the first outer loop, we can define the y range for the first iteration. With x = 0, we know that y will range from 0 to (a_size - 2) - x => 0 to (5 - 2) - 0 => 0 to 3.

These are the inner loop iterations for the first outer loop iteration:

  • y = 0 => a[0] > a[1] => 3 > 1 => Swap a[0] for a[1] => [1, 3, 5, 4, 2]

First swap - Before First swap - After

First swap - a[0] for a[1]. Images extracted from https://algorithm-visualizer.org/

  • y = 1 => a[1] > a[2] => 3 > 5 => No swap is needed  => [1, 3, 5, 4, 2]

No swap

No swap - a[1] for a[2]. Image extracted from https://algorithm-visualizer.org/

  • y = 2 => a[2] > a[3] => 5 > 4 => Swap a[2] for a[3] => [1, 3, 4, 5, 2]

Second swap - Before Second swap - After

Second swap - a[2] for a[3]. Images extracted from https://algorithm-visualizer.org/

  • y = 3 => a[3] > a[4] => 5 > 2 => Swap a[3] for a[4] => [1, 3, 4, 2, 5]

Third swap - Before Third swap - After

Third swap - a[3] for a[4]. Images extracted from https://algorithm-visualizer.org/

In the second outer loop, having x = 1, we know that y will range from 0 to (a_size - 2) - x => 0 to (5 - 2) - 1 => 0 to 2.

These are the inner loop iterations for the second outer loop iteration:

  • y = 0 => a[0] > a[1] => 1 > 3 => No swap is needed  => [1, 3, 4, 2, 5]

No swap

No swap - a[1] for a[2]. Image extracted from https://algorithm-visualizer.org/

  • y = 1 => a[1] > a[2] => 3 > 4 => No swap is needed  => [1, 3, 4, 2, 5]

No swap

No swap - a[1] for a[2]. Image extracted from https://algorithm-visualizer.org/

  • y = 2 => a[2] > a[3] => 4 > 2 => Swap a[2] for a[3] => [1, 3, 2, 4, 5]

Fourth swap - Before Fourth swap - After

Fourth swap - a[2] for a[3]. Images extracted from https://algorithm-visualizer.org/

In the third outer loop, having x = 2, we know that y will range from 0 to (a_size - 2) - x => 0 to (5 - 2) - 2 => 0 to 1.

These are the inner loop iterations for the third outer loop iteration:

  • y = 0 => a[0] > a[1] => 1 > 3 => No swap is needed  => [1, 3, 2, 4, 5]

No swap

No swap - a[1] for a[2]. Image extracted from https://algorithm-visualizer.org/

  • y = 1 => a[1] > a[2] => 3 > 2 => Swap a[1] for a[2] => [1, 2, 3, 4, 5]

Fifth swap - Before Fifth swap - After

Fifth swap - a[1] for a[2]. Images extracted from https://algorithm-visualizer.org/

In the fourth outer loop, having x = 3, we know that y will range from 0 to (a_size - 2) - x => 0 to (5 - 2) - 3 => 0 to 0.

This is the inner loop iteration for the fourth outer loop iteration:

  • y = 0 => a[0] > a[1] => 1 > 2 => No swap is needed  => [1, 2, 3, 4, 5]

No swap

No swap - a[1] for a[2]. Image extracted from https://algorithm-visualizer.org/

At the end of the final outer loop iteration, the array is ordered.

Array - Final

Array - Final. Image extracted from https://algorithm-visualizer.org/

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 1: O(n)

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

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.

Sorting 1000 different arrays with 1000 randomly sorted elements
Algorithm Average Time Spent (seconds)
Bubble Sort - Crescent 0.1692008710
Bubble Sort - Decrescent 0.1692168897
Bubble Sort Optimized - Decrescent 0.1702736743
Bubble Sort Optimized - Crescent 0.1704675061

Sorting 1000 different arrays with 1000 elements in ascending order
Algorithm Average Time Spent (seconds)
Bubble Sort Optimized - Crescent 0.0002299576
Bubble Sort - Crescent 0.0985148017
Bubble Sort - Decrescent 0.2519824719
Bubble Sort Optimized - Decrescent 0.2563169790

Sorting 1000 different arrays with 1000 elements in descending order
Algorithm Average Time Spent (seconds)
Bubble Sort Optimized - Decrescent 0.0001915042
Bubble Sort - Decrescent 0.0890307055
Bubble Sort - Crescent 0.2373096692
Bubble Sort Optimized - Crescent 0.2435169295

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!

  1. Auxiliary Space + Input space

  2. Extra or temporary space used by the algorithm during it's execution.

  3. Python's way of swapping two values dismisses the need of a temp variable to make the swap of values. Because of that, there is no use of auxiliary space in Python for the normal implementation. However, the optimized implementation still uses O(1) auxiliary space.