Ryan Dunton

Posted on Jan 15, 2019

Bubble Sort Javascript Bubble Sorting for Beginners in JS

#javascript #algorithms #sort

As someone who uses Javascript all day, every day for work I realized I took a lot of basic algorithm tasks for granted so I have decided to dive into the basics in blog posts for the next few weeks, starting today with BUBBLE SORT.

What is Bubble Sort?

Bubble Sort is a method for sorting arrays by comparing each array element to the element behind it. So, if you had an array with [3,5,4, 2] the bubble sort function would compare "3" to "5" then compare "5" to "4" and so on until the array is sorted.

Best Way to Bubble Sort

The best way I have found/built to bubble sort looks like the below:

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

Code Breakdown

Now let's break this code down snippet by snippet.

const bubbleSort = arr => {
  let swapped;
  do {} while (swapped);
  return arr;
}

Here we initialize a swapped variable and set up a do/while loop to run while swapped is equal to true, then return the array.

const bubbleSort = arr => {
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < arr.length; i++) {
      // do stuff here  
    }
  } while (swapped);
  return arr;
}

Now we have set up the function to loop over each element of the array.

const bubbleSort = arr => {
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] > arr[i + 1]) {
        // if element > the next element
      } 
    }
  } while (swapped);
  return arr;
}

If the element is greater than the element behind it in the array we want to do something (swap) with it.

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

We need to save the arr[i] element to the tmp variable because we are going to overwrite it with the value of the element behind it (arr[i+1]). Then we reassign the value of the element behind it (arr[i+1]) to equal tmp.

This was my best try at a basic Bubble Sort function, let me know if you find a more elegant solution!

Top comments (5)

Marco Antonio Dominguez • Jan 17 '19

In some cases the best solution is the one use less operations to perform any task, some of them takes the memory usage, anyhow at least for this one you have to check the operations you are performing to solve this one.

I found something weird, is a bit complex to mentally process at first glance, anyhow it takes more steps that it should.

First:

(function (a) {
/*Wrapped code to avoid issues with global scop, for quicker experiment*/
let operations = 0; 
const bubbleSort = arr => {
  let swapped;
  do {
    swapped = false;
    /* The length is calculated each iteration and most important, you iterate over the entire array multiple times */
    for (let i = 0; i < arr.length; i++, operations++) {
      if (arr[i] > arr[i + 1]) {
        let tmp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = tmp;
        swapped = true;
      }
    }
  } while (swapped);
  console.log('Operations:', operations) // Operations: 884
  return arr;
};
bubbleSort(a) 
})([1,2,6,9,4,1,2,3,5,67,8,9,2,23,5,67,7,678,2,12,34,546,567,678,890,678,34,3453,123,345,46,57,678,4])

You can create an "optimized solution cutting of some iterations"

(function(a) {
   /*wrapping to avoid global scope*/
   let operations = 0;
   const bubbleSort = (arr) => {
     /* allocating size one time and cutting some iterations starting a second loop on the n+1 array*/
     for(let i = 0, size = arr.length; i < size; i++) {
        for(let e = i+1; e < size; e++, operations++) {
            if (arr[i] > arr[e]) [arr[i], arr[e]] = [arr[e], arr[i]]
        }  
     }
     return arr
   }
   bubbleSort(a)
   console.log('Operations', operations) //Operations 561 
   /*wrapping to avoid global scope*/
})([1,2,6,9,4,1,2,3,5,67,8,9,2,23,5,67,7,678,2,12,34,546,567,678,890,678,34,3453,123,345,46,57,678,4])

This is just an experimental case, but in some cases it can crash the app or being unable to perform a task ;)

Ryan Dunton • Jan 17 '19

thanks!

Anastasiia • May 3 '19 • Edited

I was trying to figure out how to efficiently implement different kinds of sorting algorithms in ES6 style and that's what I've came up with for bubble algorithm:

Basically, it's the same as yours, but it uses .map() method instead of for loop and destructuring to swap elements. It also uses 132 Operations, if testing like Marco showed here.

Hans • Jun 3 '20 • Edited

I just modified yours and was curious what would happen if I used ~500 random numbers, assigned to const and frozen... Using object.freeze alone makes a such a MASSIVE impact, I didn't realize...

// RESOURCES:
// 
// Video Describing Bubble Sort Process
//    https://www.youtube.com/watch?v=6Gv8vg0kcHc
// IIFE Stuff
//    https://flaviocopes.com/javascript-iife/
// Bubble Sorting Post & Discussion (Read Comments!)
//    https://dev.to/ryan_dunton/bubble-sorting-for-beginners-in-js-2opp 
// Destructuring
//    https://hackernoon.com/temporary-swap-vs-xor-swap-vs-destructuring-assignment-easy-swap-7e3f1f047db5


// generate random numbers (not concerned about performance here)
        var arr = [];
        for (var i = 0; i < 500; i++)
        {
            arr.push(Math.floor(Math.random() * 499) + 1)
        }
        console.log(arr);

/*
1. use const to avoid reassignment mutations and 
2. lock it dock further by freezing the object... (speeds it up 4x)
   Comment out object.freeze to see a massive drop in preformance...
3. TODO: Experiment with TypedArrays and fill method ?
*/
// const data = [1, 2, 6, 9, 4, 1, 2, 3, 5, 67, 8, 9, 2, 23, 5, 67, 7, 678, 2, 12, 34, 546, 567, 678, 890, 678, 34, 3453, 123, 345, 46, 57, 678, 4];
const data = arr;
Object.freeze(data);

// use a function expression to avoid hoisting & const to avoid global namespace of function name
const bubbleSort = (arr) => {
  // use map instead of loop to use temp values & avoid mutations of original data.
  arr.map(ary => {
    arr.map((num, i) => {
      // compare arr[i] (left) with arr[i + 1] (right)
      // if left is greater than right, swap them via destructuring
      if (arr[i] > arr[i + 1]) {
       [arr[i+1], arr[i] ] = [arr[i], arr[i+1]]; 
      }
    })
  })
  return arr;
};

/*
PERF TESTING: 
132 Originally... 
408 By freezing the array...
1. ; Prevents issues when blindly concatenating two JavaScript files
2. Wrapped code to avoid issues with global scop, for quicker experiment
*/
;((a)=> {
  /* */
  let operations = 0;
  const bubbleSort = (arr) => {
    arr.map(ary => {
      arr.map((num, i) => {
        if (arr[i] > arr[i + 1]) {
          [arr[i+1], arr[i] ] = [arr[i], arr[i+1]]; 
          operations++;
        }
      })
    })
    return arr;
  }
  bubbleSort(a)
  console.log('Operations: ' + operations)
})(data)

Samuel James • Nov 26 '19 • Edited

Since an array starts from index 0. I would do this:

const bubbleSort = arr => {
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < arr.length-1; i++) {
      if (arr[i] > arr[i + 1]) {
        let tmp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = tmp;
        swapped = true;
      }
    }
  } while (swapped);
  return arr;
};

DEV Community

Bubble Sort Javascript Bubble Sorting for Beginners in JS

What is Bubble Sort?

Best Way to Bubble Sort

Code Breakdown

Top comments (5)

Read next

Embedding a Power BI Dashboard: A Secure and Simple Solution

Building a Collapsible UI Component in Angular: From Concept to Implementation 🚀

1760. Minimum Limit of Balls in a Bag

How to customize Strapi Dashboard / Home Page: The Right Way