Article

Bubble Sort algorithm in JavaScript

Written by

Walter G.

Published on

October 27 2019

Sorting is a common task that is required of programmers many a time. You need to sort things such as search result sets to standard lists of numbers, for reporting and such. The Bubble sort is probably the simplest of the sorting algorithms that you can implement and very popular in the coding interview community. Here is a quick implementation in JavaScript for you  to brush up on prior to your interviews.

var numbers = [3, 4, 60, 20, 2, 0];

function BubbleSort(numbers)
{
    let isSwapped = true;

    while(isSwapped)
    {
        isSwapped = false;
        for (let i = 0; i < numbers.length - 1; i++)
        {
            if (numbers[i] > numbers[i+1])
            {
                isSwapped = true;

                let tmp = numbers[i+1];
                numbers[i + 1] = numbers[i];
                numbers[i] = tmp;
             }
         }
    }

    console.log(numbers);
}

Under the hood

For the sake of this example, let us assume that we are working on sorting a typical list of numbers in an array.

var numbers = [3, 5, 200, 30, 1, 4];

The Bubble Sort algorithm will essentially compare values that are next to each other starting from the first [0, 1], [1, 2], [2, 3], etc. If we are sorting by numeric value for example in descending order, the algorithm would begin by comparing [3, 5] from the array defined above. If they indeed match the criteria, then you would swap those two values and continue with a sequential matching on the next two numbers.

The isSwapped variable is key here, as it will keep track of whether or not there was a successful comparison made. If it remains false, then we can assume that the list is fully sorted and can exit there, since no swaps were made.

Additional info

The Bubble Sort algorithm has a worst-case scenario of 0(n^2) (big 0 notation), in which 'n' is the number of numbers that will need to be sorted. The benefit of the bubble sort, however, is that it has a built-in check for when the list is completely sorted and will let us know almost immediately with the isSwapped variable. If the list is relatively close to being sorted, then the performance on this algorithm is overall pretty good. On a list that is completely unsorted however, the performance isn't ideal and there are more optimal choices.

This is a popular interview question that gets asked alot, mainly because it is quick to implement, can be written in almost any language and is still somewhat complex enough where you would need to stop and think for a minute, if you are not familiar with the algorithm.

Happy list sorting.

- Walt

Comments

No messages posted yet

Add comment