Inputs

Example List Input: [ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ]

So, let's breakdown what the input is for Bubble Sort. It's any unordered list, I mean, why sort something that is already sorted? I've never done that... (Okay, maybe I have. I didn't read the SQL! Whoops. 😅)

All jokes aside, Bubble Sort is a quick way to sort small data sets. Other sorting algorithms are more wisely used, but most of the time, let the language you're using to do it for you. This doesn't excuse you from knowing different use cases that we'll discuss in the Big O Notation post.

Key Points:

  • Unordered List
  • Number of elements, in the list, should be small
  • Inefficient
  • Quick and easy to write

Outputs

Taking the example list above we should get one like this.

Example List Output: [ 1, 2, 3, 4, 5, 6, 7,8, 9, 10 ]

Pretty simple as a human, we know the order by seeing it. With computers, we need to tell it a set of instructions to follow so that it gets the results we want. So, let's write the process down in English and then we'll break down how to write the code later.

Pseudo-code

Step 1. Given an unordered list, ex. [ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ], call it setOfNumbers.

So this can be any unordered list. I use the above list as an example to easily demonstrate the Bubble Sort algorithm.

Step 2. Create three variables called; outerIndexKeeper, innerIndexKeeper, and theSwappingValue. Set both indexKeepers to start at the first element in the list.

outerIndexKeeper and innerIndexKeeper: start at the first index, zero (0), for both variables because that's where most array indices start in programming languages.

Well, why do we have these *IndexKeepers? We need to loop through the array multiple times to ensure the elements are in the right order. This is because outerIndexKeeper makes sure we look at each element in the list and innerIndexKeeper ensures we continue to bubble up the smaller values (and have the bigger values sink to the end/bottom of the list).

theSwappingValue: This variable is to temporarily, temp for short, store one value that we need to switch when the higher index's value is less than the lower index's value. So, this allows us to switch the order of the values without losing one in the process. We'll see how that works below.

Note: If we wanted this to be in descending order, we'd check if the higher index's value is greater

Step 3. Given a list of elements called setOfNumbers, for each element in the list check to make sure it is in the right order, incrementing outerIndexKeeper.

This step ensures that each item is being checked for correct order. Because lists start at index 0, we need to go to setOfNumbers-1, to look at each item in the list. In the following step, we will actually do the comparison to determine if a swap is needed.

Step 4. Given a list of elements called setOfNumbers, for each element minus the outerIndexKeeper minus 1, check if we need to swap values.

This is the inner loop. The inner loop controls that the largest is sorted to the end of the list. We subtract outerIndexKeeper because it ensures we don't check an element that we've already sorted after the first pass.

The additional minus 1 to ensure that we stay within the bounds of the array on our first pass since the last element is going to be checked if it needs to be swapped or not when we get to the second to last element of the list.

Let's take a look at what the swap looks like next.

Step 5. If setOfNumbers[innerIndexKeeper] is less than setOfNumbers[innerIndexKeeper+1], then assign theSwappingValue to setOfNumbers[innerIndexKeeper], setOfNumbers[innerIndexKeeper] to setOfNumbers[innerIndexKeeper+1] and setOfNumbers[innerIndexKeeper+1] to theSwappingValue.

Okay, let's break this down a bit. There's two major things going on here. One is the condition check if the elements should be swapped. The other, does the swapping of the values.

The conditional check is where we make the decision if two values need to switch positions in the list. This is where theSwappingValue comes into play. The role of the variable is to help us not lose one of the values that we need to swap.

If we didn't have theSwappingValue, it'd be like us forgetting the values we were swapping in our short term memory. Computers can't just look up (like we can with our eyes) a value once it has been change.

TODO: Should I expand upon how to make Bubble Sort do ascending/descending?

Example

TODO: Walkthrough of the example steps with a sample list.

TODO: Link to a video walking through an example with playing cards.

Code

Here's the link to the code repository that I've made for this little project. It's pretty simple right now in terms of commands. The long term goal of this repository, in terms of code, is tests and to house this website's project code.

TODO: Walkthrough the code. The below is the old code and not the updated code.

TODO: Link to a video walking through the code.

Tests

Feel free to check out the tests cases I've created here. I've written two that I think are important to test. Use the npm test command when you want to run the tests.

The first test just ensures that the array is correctly sorted from descending order into ascending order.

  • Given: a set of descending numbers; 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,
  • When: Bubble Sort is called on the set of descending numbers,
  • Then: the sorted set of numbers should be; 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

The second test I created is to ensure that if a number is bigger than a previous value that was swapped, that we still order it correctly. This ensures that we leave a value out of order.

  • Given: a set of descending numbers; 10, 9, 11, 7, 6, 5, 4, 3, 2, 1,
  • When: Bubble Sort is called on the set of numbers,
  • Then: the sorted set of numbers should be; 1, 2, 3, 4, 5, 6, 7, 9, 10, 11.

As you can see, this ensures that even though 10 swapped with 9 but not swapped with 11 during our first pass, that we still get 10 at the second to last element in the list.

Overall, the test cases for Bubble Sort are pretty simple.

Big O(n)

TODO: Break down why notation is O(n)^2 and consider giving Big O Notation it's own page for algorithms

Let's take a look at the Big O notation.

Complete Video Walkthrough

TODO: Create a playlist of the video walkthroughs above

TODO: Provide a list of links to each walkthrough video