Bubble Sort in a nutshell — how, when & where

knowledge snippets for your next technical test, JavaScript edition

Let’s be honest, if you’re self-taught, there’s a high chance that algorithm topics wouldn’t even be on your radar. In part, it’s because you’re most likely preoccupied with other things — like getting your application to run, figuring out why your npm commands aren’t doing what it’s supposed to be doing or why your code is throwing errors.

Algorithms seem like a strangely academic exercise that’s quartered off to computer science graduates.

But the idea of algorithms has its place in code. It was created as a way to deal with data and how to sort into the desired order.

Not all algorithms are the same and some are better than others in certain situations. It is one of the reasons why testing your algorithmic knowledge and understanding is a common thing in technical screening tests. If you don’t know how to properly and effectively work with data, then there’s a chance that your code may not be as efficient as it possibly can.

Bubble sort is one of many algorithms that may come up in your next technical test. Here’s a quick low-down on how it works, when and where you’d use it and why you might end up using it in JavaScript instead of sort()


How it works

Imagine you have an array — [5, 3, 8, 2] — and your task is to sort them into the right order.

The idea behind bubble sort is that you’re comparing two adjacent values with one other. If the value on the left is bigger, you swap it with the one on the right.

bubble sort by Aphinya Dechalert

You keep doing this for your entire dataset and your biggest value eventually bubbles up to the top (aka. the right-hand side).

first round completed.

Once the confirmed biggest value is its final position, a partition is created and that value doesn’t need to be compared again, saving you processing time.

In our case, 8 will get partitioned when the algorithm runs again and the comparator decides that there is no bigger value than it.

Here is the second round running of the bubble sort algorithm.

5 is small than 8 and 8 has nothing to compare to, so a partition is formed.

The algorithm will keep running until all the values are sorted.

And that’s basically bubble sort in a nutshell.

Here is an animated version I created to help illustrate the process.

Bubble Sort animated gif by Aphinya Dechalert.

The code

Now that we’ve got the theory, how do we translate the above idea into code? Take a look at the pseudo-code below.

for i from 1 to N
for j from 0 to N -1
if a[j] > a[j + 1]
swap( a[j], a[j + 1])

Let’s translate this code into picture form to help you understand how it’s applied.

So that’s the pseudo-code, but what does it look like in JavaScript?

Here is a version of the translated pseudo-code.

let bubbleSort = (yourArray) => {
let arrSize = yourArray.length; //this will give you the first N
let swapped;
do {
swapped = false;
for(let i = 0; i < arrSize; i++){
if(yourArray[i] > yourArray[i + 1]){
//where the swap happens
let tmp = yourArray[i];
yourArray[i] = yourArray[i+1];
yourArray[i+1] = tmp;
swapped = true;
}
}
} while(swapped);
return yourArray;
}

The above code is a function that you can run for a simple array in JavaScript and is a direct translation of the pseudo-code above. There are alternative ways to write and implement bubble sort, and the above code is only one of the potential translations.


When & Where

The question now leads to, when and where would you ever use bubble sort? JavaScript already has a sort() method, something which I’ve discussed in-depth here.

But sometimes, sort() just doesn’t cut it because it’s taking too long. This is because in JavaScript, sort() is implemented differently by the JavaScript interpreter and you have no control over how things are done. When you write your own algorithms, you decide how things are done.

Bubble sort works well with large datasets where you know that items are almost sorted. For example, you might have a school roll of 1000 children. Each child belongs to a grade — which means that age-wise, they are already semi-sorted.

Another example may be a large company with employees put into different departments and roles ranking. It’s expected that within these groups, there is already a pre-determined range of salaries. So if you’re given the entire dataset to sort, they’ve already been pre-sorted based on department and roles.


Final words

So that’s bubble sort in a nutshell. It’s a common question that sometimes comes up in technical tests, so it’s good to at least know what it’s about and how it works.

Report

What do you think?

Leave a Reply

Your email address will not be published. Required fields are marked *

Loading…

0

Comments

0 comments

The Things You Need to Consider for Your Coding Portfolio

The Low Down on Attribute and Structural Directives in Angular