Algorithms for Beginners: Bubble Sort in JavaScript

Algorithms are a fundamental part of software and coding. Algorithm is this fun buzzword that makes something sound really complicated and cool. I’d like to point out that an “algorithm” literally is just a way of doing something; it’s just a process. Nonetheless Algorithms and Data-Structures are a core part of software because at the end of the day you are just working with data. Data needs to be organized for it to be meaningful just like the letters on this page. Atwh and whAt have the same letters but the latter has meaning because of the organization.

When we talk about “Algorithms” in software and coding we really just mean a specific way to organize specific data. One of the best parts of working in software is that there is no one “correct” way to do something. If it works it works. However there are ways that things can be optimized. Here is a resource on how to optimize for time complexity and space complexity. All that means is we need to account for how much memory and how much time something takes. One of the easiest Algorithms, which isn’t used in “production”, is Bubble sort.

Bubble sort has a lot of time complexity. It’s BigO² or O(n²) meaning it takes time. For a small snippet this is not really noticeable. However if you are professionally building something that same calculation or logic could take minutes, even tens of minutes as the data weight increases. Bubble Sort is useful to help you get started on learning Algorithms. As a beginner think about the problem:

“How to order an array of numbers smallest to largest?”

Because we are beginning we are going to use the Brute Force technique which ironically is what bubble sort exactly does. In general terms lets start a “for loop” and iterate over the array and look at each element compared to the next element (

element +1

) at a time; (element > element + 1). If this statement returns true then you will swap them. Again using brute force how would you do that? I’m sure you can think of ways to do this.

Then the solution is totally simple.

We just assign

array[i] = array[i+1]

. To assign

array[i+1]

to the value of

array[i]

you must create temporary storage slot.

I’ll explain why is a few sentences why.

Let’s walk through what is happening line by line:

We have a function named bubble after the “bubble sort” algorithm we are about to use. A variable named recursion set to false. We use the term because the function will call itself until it is sorted. If we have to preform a swap of any of the elements in the array we will reset recursion to true because it will have to call itself again. If a swap happens then the array is not sorted yet. On line 5 we have an “if” condition.

If the element before the next element is bigger then we set recursion to true and then the swap procedure is preformed. Then we create a variable and call it “storage”. Storage will hold the value that is being moved. We do this because we are about to overwrite it. Next on line 9 we set the element with the lower value to the the lower slot in the array(array[i]; we reassign the element. Now the higher element is overwritten to the lower element value.

With assignment; if you know your precedence of operations ; you can see what is happening. We see the = operator which will run right to left; what is on the left of = is then assigned to what is on the right. The value on the right of the "=" operator will be assigned to the variable on the left. With an array of

[5,3,1]

on the first pass, storage will be

5

, and here on line 9 we set

array[0]

to

3

(this is the

array[i+1]

). Because storage is now

5

we can use it to replace

array[i+1]

with it. We can no longer use

array[i]

because at this point it is now

3

.

Bubble sort swaps values adjacent to each other. We need to put 5 where

3

is right now. In this instant of time or at this “tangent” of values

3

is both at

array[i]

and

array[i+1]

. Here JavaScript is annually using “Pass by Value”. We know this because “storage” was set to

array[i]

. This reference or

array[i]

is currently

3

. The number

5

is a primitive datatype and thus JavaScript uses a pass by value here.

No matter what

array[i]

is storage will always be

5

at this point; unless it is reassigned. JavaScript has assigned storage to the “address” in memory that is allocated to the primitive datatype

5

. We thus use the storage variable to assign

array[i+1]

to storage;

array[i+1]

is now

5

. The array at this point in time looks like

[3,5, 1]

.

Terminal/Console for bubble.js

You can see in the js file above there are console.logs of what the code is doing. I put in the logic gate of (

array[i] > array[i+1]

) so you can see when this returns false and does not run.

At the end this is always false and thus recursion is never assigned to ‘ture’. Bubble sort then returns the array.