Mahijendra B V K

Mahijendra B V K

Bubble Sort in JavaScript

Bubble Sort in JavaScript

Bubble Sort, sometimes also referred to as Sinking Sort is one of the most widely known sorting algorithms. It is usually one of the first sorting algorithms that CS students come across due to its simplicity and the fact that it is quite intuitive and easy to translate into code.

However, this simple algorithm has shown poor performance in real-life problems. Especially compared to faster, more popular, and widely used algorithms like Quicksort or Merge Sort. This is why Bubble Sort is used primarily as an educational tool.

In this article, we'll explain how Bubble Sort works and implement it in JavaScript. We will also check out its time complexity, and compare it to some other sorting algorithms.

Bubble Sort

Bubble Sort is a comparison-type sorting algorithm. This means that it compares individual elements within the collection during runtime. Depending on your data type and purpose, the comparison can be done via a relational operator or through a custom comparison function.

The idea behind Bubble Sort is rather simple. Starting from the beginning of the collection we want to be sorted - we compare elements within a pair. If the pair is in the desired order, we do nothing. If it isn't, we swap the elements it consists of.

This is done again, and again, until all elements in the collection are sorted. Let's look at a visual representation of how Bubble Sort works:

bubble-sort-in-java-1.gif

Taking a look at the element with the value of 8, we can see it "bubbling up" from the beginning of the array to its proper place. This is where the name Bubble Sort comes from.

Bubble Sort Implementation

Now that we've gone over the idea behind Bubble Sort, we can start with the implementation:

function bubbleSort(inputArr) {
    let n = inputArr.length;

    for(let i = 0; i < n; i++) {
        for(let j = 0; j < n; j++) {
            // Comparing and swapping the elements
            if(inputArr[j] > inputArr[j+1]){
                let t = inputArr[j];
                inputArr[j] = inputArr[j+1];
                inputArr[j+1] = t;
            }
        }
    }
    return inputArr;
}

The implementation is pretty intuitive. We iterate through the array n times with a for loop, where n is the length of the array. For each iteration, we "bubble up" an element to its correct place. This is done through another for loop that compares the element to its adjacent one, switching them if need be.

Finally, we return the sorted array. Let's populate an array and sort it:

let inputArr = [5,1,4,2,8];
bubbleSort(inputArr);
console.log(inputArr);

Running this code will yield:

(5) [1, 2, 4, 5, 8]

Let's take a look at how this is done with concrete values:

First iteration:

[5, 1, 4, 2, 8] -> [1, 5, 4, 2, 8] - We are swapping 5 and 1, since 5 > 1
[1, 5, 4, 2, 8] -> [1, 4, 5, 2, 8] - We are swapping 5 and 4, since 5 > 4
[1, 4, 5, 2, 8] -> [1, 4, 2, 5, 8] - We are swapping 5 and 2, since 5 > 2
[1, 4, 2, 5, 8] -> [1, 4, 2, 5, 8] - No change, since 5 < 8

Second iteration:

[1, 4, 2, 5, 8] -> [1, 4, 2, 5, 8] - No change, since 1 < 4
[1, 4, 2, 5, 8] -> [1, 2, 4, 5, 8] - We are swapping 4 and 2, since 4 > 2
[1, 2, 4, 5, 8] -> [1, 2, 4, 5, 8] - No change, since 4 < 5
[1, 2, 4, 5, 8] -> [1, 2, 4, 5, 8] - No change, since 5 < 8

The array is sorted within two iterations, however, our algorithm will continue running n times, comparing all the elements over and over again. This is because we've told it to iterate inputArr.length times.

Bubble Sort is inefficient in and of itself - especially with a flaw like this. There are two things we can do to optimize it, though.

Bubble sort has the following performance cases:

Since our array contains n elements, Bubble Sort performs O(n) comparisons, n times. This leads us to a total running time of O(n2) - average and worst-case. This is a horrible time complexity for a sorting algorithm.

For reference, most common sorting algorithms, such as Quicksort or Merge Sort, have an average running time of O(nlogn).

Worst-case time complexity: Big O (n^2).

Average-case time complexity: Big theta (n^2).

Best-case time complexity: Big omega (n).

Space complexity: Big O (1).

Check out the code down here :)

See the Pen Bubble Sort by B V K MAHIJENDRA (@mahijendra) on CodePen.

Conclusion

Although Bubble Sort is very intuitive and easy to understand and implement, it is highly impractical for solving most problems.

It has an average and worst-case running time of O(n2), and can only run on its best-case running time of O(n) when the array is already sorted.

Its space complexity is O(1), which is great. Unfortunately, that's not nearly enough to make up for the awful time complexity.

Even among simple O(n2) sorting algorithms, Insertion Sort or Selection Sort are usually considerably more efficient.

Due to its simplicity, Bubble Sort is often used as an introduction to sorting algorithms at introductory computer science courses.

Thank you for reading! Happy coding♥️

 
Share this