Implementing Bubble Sort in Javascript

In this article, we cover breakdown Bubble Sort and then also share its implementation in Javascript.

Firstly, let's get it out of the way. When we say "sort", the idea is to re-arrange the elements such that they are in ascending order.

If you are new to the concept of sorting, each section of the article would be useful - concept of bubble sort, its algorithms, efficiency, etc. However, If you are here to refresh your knowledge, jump straight to the javascript implementation of the sort. Go to code

Table of Contents

• Explanation of Bubble Sort
• Code - Implementing Bubble Sort using Javascript
• Visualization
• Complexity of Bubble Sort
• Other Related Concepts

 

Explanation of Bubble Sort

If you are a newbie to sorting, Bubble sort is a great place to start! It is one of the more intuitive sorting methods as its algorithm mirrors how our brain generally thinks about sorting - by comparing.

Let's remove the vagueness and delve deeper into it.

A. What Bubble Sort Does?

To achieve sorting in Bubble Sort, the adjacent elements in the array are compared and the positions are swapped if the first element is greater than the second. In this fashion, the largest value "bubbles" to the top.

Usually, after each iteration the elements furthest to the right are in correct order. The process is repeated until all the elements are in their right position.

B. What Bubble Sort Does?

1. Starting with the first element, compare the current element with the next element of the array.

2. If the current element is greater than the next element of the array, swap them.

3. If the current element is less than the next element, just move to the next element.

4. Start again from Step 1.

C. Illustrating the Bubble sort method

Iteration 1: [6,4,2,5,7] → [4,6,2,5,7] → [4,2,6,5,7] → [4,2,5,6,7] → [4,2,5,6,7]

Iteration 2:[4,2,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7]

Iteration 3: [2,4,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7]

Other Alternatives

As you might have noticed, Bubble Sort only considers one element at a time. Thus, it is highly time consuming and inefficient. Due to its inefficiency, bubble sort is almost never used in production code.

You can use a built in function Array.prototype.sort() for sorting. This is an inplace algorithm just like bubble sort which converts the elements of the input array into strings and compares them based on their UTF-16 code unit values. Also, if you are interested, you can read about index sort which is another simple comparison based sort method that has a better performance than Bubble sort.

Implementing Bubble Sort using Javascript

Now as we have seen the logic behind bubble sort, we can write the code for it in a straightforward manner, using two nested loops.

 

 

let bubbleSort = (inputArr) => {
    let len = inputArr.length;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            if (inputArr[j] > inputArr[j + 1]) {
                let tmp = inputArr[j];
                inputArr[j] = inputArr[j + 1];
                inputArr[j + 1] = tmp;
            }
        }
    }
    return inputArr;
};

As you can see here, the sorting function will run until the variable "i" is equal to the length of the array. This might not be the most efficient solution as it means the function will run on an already sorted array more than once.

A slightly better solution involves tracking a variable called "checked" which is initially set to FALSE and becomes true when there is a swap during the iteration. Running this code on a do while loop to run the sorting function only when "checked" is true ensures that the function will not run on a sorted array more than once.

 

 

let bubbleSort = (inputArr) => {
    let len = inputArr.length;
    let checked;
    do {
        checked = false;
        for (let i = 0; i < len; i++) {
            if (inputArr[i] > inputArr[i + 1]) {
                let tmp = inputArr[i];
                inputArr[i] = inputArr[i + 1];
                inputArr[i + 1] = tmp;
                checked = true;
            }
        }
    } while (checked);
    return inputArr;
 };

 

Visualization

If you are finding it hard to visualize Bubble Sort, you can check this website https://visualgo.net/bn/sorting?slide=1.

You can play around with the code and see the specific function of each part of the code and how they play together to get the final sorted array.

Complexity of Bubble Sort

The worst case scenario: quadratic O(n²): this is the case when every element of the input array is exactly opposite of the sorted order.

Best case scenario: linear O(n): when the input array is already sorted. Even in this case, we have to iterate through each set of numbers once.

The space complexity of Bubble Sort is O(1).