# Bubble sort

###
James Robb
*Updated on *
・2 min read

Algorithms (7 Part Series)

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.

Algorithms (7 Part Series)

With

`const next = inner + 1`

won'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 on`output[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!