in Algorithms

Bubble Sort Algorithm

Our algorithm for Day 3 of 30 Days of Algorithms is a Bubble Sort. Bubble Sort is not an efficient sort algorithm (The Big-O notation for the time complexity is 0n2) but it is useful for learning. The basic premise is very simple : Start with the first two items in the list. If the first item (left) is higher than the second item (right), swap them.

After comparing items 1 and 2, proceed to items 2 and 3. Then 3 and 4, etc. Once the algorithm has gone through all numbers, or cannot swap the two numbers being compared, go back to the beginning and start again. This process is repeated until all numbers are in the proper order.

About the Bubble Sort Code

Most often when you see code examples for Bubble Sort, a temp variable is used to hold one of the two values being swapped. JavaScript ES6 has a nice feature that makes this unnecessary. We can use the properties of JavaScript arrays to swap both numbers simultaneously. So on the line that reads, [ x[i], x[i + 1] ] = [ x[i+1], x[i] ] we are simply swapping items x(1) and x(2) with one another and do not need a temp variable.

Code Example

You can also grab the gist from my Github account.

/**
 * Bubble sort.
 * @param a
 * @returns {*}
 *
 * Big-O : O(n2)
 */
const bubble_sort = (a) => {

    let swap = true,
        n = a.length-1,
        x = a;

    while (swap) {
        swap = false;
        for (let i = 0; i < n; i++) {
            if (x[i] > x[i+1]) {
                /*
                 * We're just swapping the i &amp; i + 1 
                 * items in the array without using a 
                 * temp variable.
                 */
                [ x[i], x[i + 1] ] = [ x[i+1], x[i] ];
                swap = true;
            }
        }
        n--;
    }
    return x;
}


var a = [
    62, 52, 88, 51, 26, 40, 13, 44,
    83, 30, 10, 31, 99, 79, 81, 45,
    33, 97, 17, 96, 38, 50, 39, 22,
    47, 61, 20, 85, 10, 16, 15, 95,
    11, 71, 21, 86, 24, 28, 46, 5,
    89, 54, 70, 87, 35, 42, 69, 82,
    84, 76, 60, 98, 77, 68, 8,  66,
    96, 78, 90, 75
];

console.log(
    "Inputs : [ " + a.join(', ') + " ] \n" +
    "Sorted : [ " + bubble_sort(a).join(', ') + " ]"
);

You can grab the code from my Github repository for the 30 Days of Algorithms series. Feel free to leave feedback or ask questions in the comments below, or reach me via the Contact Page.

Write a Comment

Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.