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
```

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]`

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

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

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

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]`

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

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

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]`

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

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]`

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

## 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!

Auxiliary Space + Input space ↩

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

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. ↩