Originally sent to subscribers of the BaseClass newsletter
Probably the simplest of sorting algorithms, Bubble Sort is inefficient at scale but quick to write and works fine on a handful of elements.
It is an excellent introduction to more complex sorting algorithms.
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.
Let's go...
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 4 elements in the list, which means we'll need to repeat our loop 3 times.
Why 3? Because once 3 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 n-1.
Here's the state of our array after each pass. The sorted elements after each loop are highlighted.
Here's the JavaScript code for this algorithm:
// We need to repeat the algorithm n-1 times
for (let loop = 0; loop < array.length - 1; loop++) {
// Loop through each pair of elements
for (let pair = 0; pair < array.length - 1; pair++) {
// Is this pair the wrong way around?
if (array[pair] > array[pair + 1]) {
// Make the swap (using temporary variable)
let tmp = array[pair]
array[pair] = array[pair + 1]
array[pair + 1] = tmp
}
}
}
We can improve on this basic algorithm though, with a couple of optimisations.
Optimisation #1
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 very slightly quicker.
Here's the updated code. Notice that the limit for the inner loop is now array.length - loop - 1:
for (let loop = 0; loop < array.length - 1; loop++) {
for (let pair = 0; pair < array.length - loop - 1; pair++) {
if (array[pair] > array[pair + 1]) {
let tmp = array[pair]
array[pair] = array[pair + 1]
array[pair + 1] = tmp
}
}
}
Optimistion #2
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 optimisation; 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:
for (let loop = 0; loop < array.length - 1; loop++) {
let hasSwapped = false;
for (let pair = 0; pair < array.length - loop - 1; pair++) {
if (array[pair] > array[pair + 1]) {
let tmp = array[pair]
array[pair] = array[pair + 1]
array[pair + 1] = tmp
hasSwapped = true;
}
}
if (!hasSwapped) {
// No swaps, the array is now sorted
break;
}
}
Want to know more?
Check out these links:
Latest comments (0)