Bubble sort is a sorting algorithm that works by repeatedly looping over a list that need to be sorted, comparing the current item and the one immediately following it. If they are in the wrong order, the values positions in the list are swapped. This is done repeatedly until no swaps are required, indicating that the list is sorted.
Implementation
Below we can see an example implementation of bubble sort using JavaScript.
function bubbleSort(input) {
const output = [...input];
const length = output.length;
for(let outer = 0; outer < length; outer++) {
for(let inner = 0; inner < length; inner++) {
const next = inner + 1;
if (output[inner] > output[next]) {
const temp = output[inner];
output[inner] = output[next];
output[next] = temp;
}
}
}
return output;
}
In this implementation we loop the array which is to be sorted into a new array which initially contains the items of the input array, this is assigned to the variable output. We run a nested loop to compare each item in the output array to all other values of the output array. If the current item is greater than the next item, we swap their positions in the output array. We do this until the loop exits and returns the final sorted array. Below you will find a visual example of bubble sort in action:
Use Case and Performance
The performance of bubble sort depends on 2 factors, namely:
- How large is the input array?
- How unsorted is the input array?
The second factor applies to almost every sorting algorithm but is still valid. The first factor is an important one though since bubble sort has a Big O time complexity of O(n²) on average. This means that the time it takes to run the algorithm is the square of the size of the input array, otherwise known as Quadratic Time.
Let's look at some example runtimes from given input sizes:
| Input size | Time complexity (Big O) |
|---|---|
| 10 | O(10²) = O(100) |
| 100 | O(100²) = O(10,000) |
| 1000 | O(1,000²) = O(1,000,000) |
Conclusions
As we can see, the larger the input array is, the worse the performance becomes. This being the case, if we use bubble sort, we want to do it on small arrays and collections to maximise performance.
Top comments (4)
With
const next = inner + 1won't you go out of range when inner = length - 1?How did you do the animation?
It won't go out of range since the
const next = inner + 1;will return undefined when we try to do a lookup onoutput[next]for the last item in the iterable.For example:
This being the case no swap happens and no error throws, in other languages it would though but this is JavaScript and so we don't need to mitigate anything here.
I got the animation from Geeks for Geeks.
OK thanks for the explanation. Good series it is a great refresher
All good. Glad you’ve been enjoying the series so far!