DEV Community

loading...

What is Bubble Sort?

davejsaunders profile image Dave Saunders Originally published at baseclass.io ・4 min read

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:

Array containing 6,9,4,3


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.

Array containing 6,9,4,3

On to the next pair. These elements are in the wrong order, so we'll swap them.

Array containing 6,4,9,3

And finally, the last pair, which also need to be swapped:

Array containing 6,4,3,9

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:

Array after the fist pass

Notice how the highest value, 9, moved up through the array and into the correct place:

Array showing that 9 has 'bubbled' up to the top

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.

All stages of the algorithm

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
      }      
    }
  }
Enter fullscreen mode Exit fullscreen mode

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
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

Optimistion #2

Imagine our algorithm was passed an array like this:

A pre-sorted array

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;
    }
  }
Enter fullscreen mode Exit fullscreen mode

Want to know more?

Check out these links:

Discussion (0)

pic
Editor guide