Basic Solutions to Sorting Algorithms: BubbleSort

I think at some point very early in my coding journey I watched a video on the BubbleSort method that went completely over my head and just thought, “Nope. That’s not for me.”

However, after getting some coding and algorithm experience under my belt, I’ve realized that I should probably stop avoiding the sorting algorithms (including BubbleSort) and get some experience solving these problems before I get asked about them at a job interview.

So, if you, like me, are studying for technical interviews and want to learn how to solve a problem like BubbleSort, I hope my quick guide can make this process less intimating for you than it was for me!

What exactly do you mean by a sorting algorithm, Hope?

Great question.

In an interview setting, sorting generally refers to sorting an array of numbers for least to greatest.

(Side note: this would be the appropriate time to judge me for avoiding this problem for months)

Well, now that we’ve got that sorted (pun intended), let’s move on to the actually implementation of this problem.

The Solution: Nested For Loops (aka the much harder part)

**if you are worried about the runtime complexity of using two nested for loops, please read my note below**

The basic goal of BubbleSort is to find the largest element in an array and drag it over to the right-hand side.

To make this happen, we are going to need two nested for loops. The first for loop will be iterating over every element in the array. The second for loop, and this is probably the most complex part of the entire problem, will be iterating over a continuously shrinking array.

Why will the second for loop want to iterate over a shrinking array? Another great question.

The first time our second for loop runs, it will, like the outer loop, also iterate over every element in the array. In doing so, it will determine which element in our array is the largest and then it will send that element to end of our array (thus putting it in it’s correctly sorted place).

However, once we’ve found the largest number in our array and sorted it into it’s correct place, we no longer need to worry about that last (and largest) number. We can, therefore, shrink the window we are looking at to only include the unsorted elements of our array.

for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < (arr.length - i - 1); j++) {
    //our sorting mechanism will go here 
  }
}

Above, you can see the window of our second for loop getting shrunk on line two. By subtracting the value of i from arr.length, we ensure that for each iteration of our outer loop we are reducing the window size of our second loop.

Ultimately, every time we iterate through a window of elements, we will find the largest element amongst them, sort it to its correct place and be able to again shrink our window.

Whew.

In my opinion, understanding how our second for loop works is probably the hardest part of this solution, so now that you (hopefully) have some understanding on how that for loop is working we can move on to the much easier task of actually getting our numbers sorted.

The Solution: Sorting (aka the much easier part)

Basically, to sort the elements, we will need to do two things.

1. We will look at the current element, ask if that element is larger than the element in front of it, and
2. if it is, swap the two elements.

The first step will be accomplished by a boolean statement comparing the values of the two elements (ex: arr[j] > arr[j+1]).

If that conditional statement is true, we can then move onto step two and swap the two elements. In order to do so, , we will make use of a new variable that I called smaller. Smaller will get assigned the value of the (you guessed it) smaller element (ex: arr[j+1]).

Once we’ve stored this value, we will then be able to reassign that elements original index to our larger element (ex: arr[j]).

After doing so, since we smartly thought to store the value of our second element in “smaller”, we can similarly reassign the spot our larger element had in our array to our smaller element.

This may seem like a lot, but it’s much more basic in practice:

let smaller = arr[j+1]
arr[j+1] = arr[j]
arr[j] = smaller

The Solution: Putting It All Together

Now that we understand the two major components of our BubbleSort solution, here is how they work together:

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < (arr.length - i - 1); j++) {
      if (arr[j] > arr[j+1]) {
        let smaller = arr[j+1]
        arr[j+1] = arr[j]
        arr[j] = smaller
      }
    }
  }
  return arr
}

Hopefully, you found this walkthrough helpful and have a better understanding on how to implement a solution to this problem (or one like it!) on your own. Solving algorithms takes practice, so if you are feeling a little lost or overwhelmed, just keep practicing and I know you will get the hang of it soon!

A Note on BubbleSort

I mentioned above that I was going to discuss the runtime complexity of this BubbleSort solution. The reality is that BubbleSort has a high worst case runtime of n² meaning that it will never be a practical algorithm for sorting large data sets (though it’s still great to use on smaller data sets!).

Ultimately, BubbleSort is a great practice problem for those of us beginning to study algorithms regardless of this runtime complexity, so don’t get too bogged down in how slow/ineffective this algorithm can potentially be!

BubbleSort is great!