Why Should I Care?
Bubble sort is an excellent introduction to sorting algorithms.
It is also useful as a reference when we cover more complex search algorithms later.
In 5 Minutes or Less
Let’s sort this array into ascending order:
Step 1: Compare Pairs of Elements
We’re going to loop through each pair of elements in turn.
If a pair of elements aren’t in the right order, we’ll swap them.
The first pair is already in the correct order, so we can ignore them.
On to the next pair. These elements are in the wrong order, so we’ll swap them.
And finally the last pair, which also need to be swapped:
We’ve now looped through all of the pairs, so our first pass through the array is done.
This is how the array looked at the beginning and end of this first pass:
Notice how the highest value, 9, moved up through the array and into the correct place:
It has ‘bubbled up’ to the correct position – hence ‘Bubble Sort.’
Step 2: Repeat
Our first pass moved the highest element, 9, into the correct place.
Each time we repeat this loop, we move the next highest element into place.
Now, we repeat this process – comparing each pair in-turn and swapping them if required – until the array is completely sorted.
We have four elements in the list, which means we’ll need to repeat our loop three times.
Why three? Because once three of the elements are in the correct place in the array, the remaining one must also be correct.
If the number of elements in our array is
n, the number of loops we’ll need is
Here’s the state of our array after each pass. The sorted elements after each loop are highlighted.
We can improve on this basic algorithm though, with a couple of optimizations.
Remember how the first pass of the algorithm caused the 9 to bubble up into the correct position?
After that first pass, we know that the last element is correctly placed, so we can ignore it on our next loop. After the second pass, the second-to-last element is sorted, and so on.
We’ll change our code to ignore the last element after the first loop, the last two after the second loop, and so on.
This will make our algorithm slightly quicker.
Here’s the updated code. Notice that the limit for the inner loop is now
array.length - loop - 1:
Imagine our algorithm was passed an array like this:
This array is already sorted, doing three loops of our sorting algorithm is a complete waste of time.
This leads us to our next optimization; if we ever complete a loop without swapping any elements, we know the array is sorted and we can stop early.
That could be a big time saving when the array is already sorted – or nearly sorted – before we even start our Bubble Sort.
With that code added, our final Bubble Sort algorithm looks like this:
Want to Know More?
Check out these links: