Bubble Sort Talk

I recently have been checking out Vue.js and decided that it's time to build something with it so I can become more familiar with its inner workings and strengths. After walking through some of the intro material, following along with a few tutorials, reading documentation, and building the preverbal ToDo app, it was time to jump in!

So... What should I build? Well, what have I been doing lately? Drinking coffee, as always, but also studying algorithms! A perfect place to start.

My plan is to craft and deploy a Vue application that shows off (visualizes) different sorting algorithms. Deciding to start with one of the most basic sorting algorithms, certainly not the most efficient, I began with Bubble Sort.

In my next post I'll dissect some of interesting solutions I came up with for actually visualizing this algorithm to the viewer. However, before I dive into the visualization I will utilize this blog post to go over how bubble sort actually sorts.

So here we go: Let's say we are given a collection of 5 integers that are not sorted and we are supposed to sort them:

[ 3, 2, 6, 9, 1 ]

Bubble sort compares the first two integers, in this case it would be the values 3 and 2. If the first one is greater than the second, bubble sort will swap them. So, because 3 is greater than 2 it will swap them in place, altering the array to look like this:

[ 2, 3, 6, 9, 1 ]

Then it performs this comparison with the next two indexes comparing the values of 3 and 6. Since 3 is not greater than 6 it will not swap them. Repeating the process again with the next indexes: 6 is not greater than 9 so they won't swap. And finally, 9 is greater than 1 so they will swap. By the time we have iterated over the whole array the largest value of the array is at the end.

[ 2, 3, 6, 1, 9 ]

Now that the largest value has been sorted to the end of the array it is in its final sorted position so we don't have to compare any other values with its value. Keeping this in mind can marginally help the efficiency of our bubble sort algorithm by only comparing indexes that are not in their final sorted position.

Next we would repeat this same process of comparing two adjacent indexes, starting with the 0th and 1st index to sort the next largest value to the end of the array. If we repeat this process n times, where n is the number of values in our array, then by the last iteration all of the values will be in their final sorted position.

Considering the efficiency of bubble sort is very interesting. At its best, bubble sort operates has O(n) time complexity. This only happens when it is given a sorted array and if bubble sort keeps track of if it has performed a swap or not.

If bubble sort was given this array

[ 1, 2, 3, 4, 5 ]

...and it kept track of whether it had to swap two values or not. Then it would iterate over this entire array one time, not needing to swap values, and then return the sorted array.

Conversely, at its worst, bubble sort gives us a time complexity of O(N²) where N is the length of the array, because we will iterate over the whole array N to place each value it its sorted position.

The space complexity is not bad since we are swapping values in place, not creating a new array so it would in constant space or O(1).

Now that we've covered the basic concept of bubble sort here is a code example that walks through and executes the same logic:

const bubbleSort = (array) => {
  let swap = true;
  let counter = 0;

  while (swap) {
    swap = false;
    for (let i = 0; i < array.length - 1 - counter; i += 1) {
      if (array[i] > array[i + 1]) {
        swap = true;
        const placeholder = array[i + 1];
        array[i + 1] = array[i];
        array[i] = placeholder;
      }
    }
    counter += 1;
  }
  return array;
};

We'll start by initializing swap to a boolean value which allows us to use it as a flag in case our list is already in order. If we ever make a pass all of the way through the list of integers and don't make a swap we can assume our list is in order and kick out of the loop returning the array.

The counter variable allows us to not have to consider comparing values to those values at the end of our array that are already in their sorted position.

Following the variables we enter a while loop that is continues only if a swap occurs. Inside of our while loop we iterate over each index comparing it's value to the one next to it. We'll swap their positions if the first value is greater than the one that follows. After an iteration through the array we will increment the counter and repeat the process until the array is completely sorted.

This is a simple yet important algorithm that helps us consider space and time complexity as well as how it might relate to other algorithms. Up next I'll explain how I was able to visualize this with some async/await functions and css properties. See you then!