What is bubble sort?
This sorting algorithm is one of the simplest to understand, and is generally the first sorting algorithm taught to beginners.
It is rarely used in the real world though, as it is outperformed by almost every other sorting algorithm.
The basic idea of the algorithm is that, given an array of values, the larger (or smaller depending on the direction we are sorting the array) values are bubbled to their correct positions in the array by iterating through the values and swapping ones that are not in the correct order.
The algorithm step-by-step
Given an array of values 2, 4, 8, 3, 7, to sort in ascending order, we need to loop through the values comparing each one to the next and if the next value is lower than this one, we swap the two values in place.
This looks something like:
At index 0
original values = 2, 4, 8, 3, 7
This value = 2
Next value = 4
Next value is greater than this so do not swap
new values = 2, 4, 8, 3, 7
At index 1
original values = 2, 4, 8, 3, 7
This value = 4
Next value = 8
Next value is greater than this so do not swap
new values = 2, 4, 8, 3, 7
At index 2
original values = 2, 4, 8, 3, 7
This value = 8
Next value = 3
Next value is less than this so swap them
new values = 2, 4, 3, 8, 7
At index 3
original values = 2, 4, 3, 8, 7
This value = 8
Next value = 7
Next value is less than this so swap them
new values = 2, 4, 3, 7, 8
After one iteration through the array, the values are still not sorted, so we need to repeat this process again.
At index 0
original values = 2, 4, 3, 7, 8
This value = 2
Next value = 4
Next value is greater than this so do not swap them
new values = 2, 4, 3, 7, 8
At index 1
original values = 2, 4, 3, 7, 8
This value = 4
Next value = 3
Next value is less than this so swap them
new values = 2, 3, 4, 7, 8
At index 2
original values = 2, 3, 4, 7, 8
This value = 4
Next value = 7
Next value is greater than this so do not swap them
new values = 2, 3, 4, 7, 8
At index 3
original values = 2, 3, 4, 7, 8
This value = 7
Next value = 8
Next value is greater than this so do not swap them
new values = 2, 3, 4, 7, 8
At this point we can visually see that the array is sorted but our algorithm does not yet know that we have finished, we need to keep iterating through the array until no swaps are performed.
Performance of bubble sort
Hopefully at this point you can see why this algorithm is so inefficient, especially for larger arrays.
Time
The best case scenario is an array that is already sorted, even then we still need to iterate through it once to confirm it is sorted, this is why the best case big O notation for this algorithm is O(n), as all n values need to be checked.
For this small array we had to iterate through it 3 times, but for the worst case, a reverse sorted array we need to iterate through it n times, where n is the size of the array e.g. sorting the values 10, 8, 6, 4, 2 would take 5 iterations, this gives a worst case big O notation for this algorithm as O(n²), as all n values need to be checked n times.
Space
Because the values can be swapped in the existing array, bubble sort can be performed without allocating any extra memory (as far as big O is concerned) therefore the space complexity is O(1)
Stability
The stability of a sorting algorithm is whether the order that identical values were placed into the unsorted array is preserved after the sort e.g. if the input values are 3, 1, 1 then, if the sorting algorithm is stable, 1 will be before 1 in the sorted array, with an unstable sorting algorithm, 1 and 1 could end up in any order.
Bubble sort is considered a stable sort, as any two identical values will not be swapped.
Example Implementation
Below is an example implementation of this algorithm in python:
Running this produces the following output:
Summary
Despite this algorithm being used very rarely in the wild, I don't think I could have started a sorting algorithms series without including it.
If nothing else the bubble sort algorithm can be used as a benchmark to compare other algorithms against.
Stay safe & Keep learning
Graham
Top comments (0)