Let’s understand Bubble sort by building a bubble sort visualiser in javascript.

Intro What is bubble sort? Big O Worst Case Best Case Average Case spatial complexity O(1)Is this sorting algorithm stable? Bubble Sort Implemented in JavaScript Implementing a bubble sort visualiser with html, css and JavaScript.

Intro

Hello world! I have just started learning sorting algorithms in javascript and in this blog I will try to explain Bubble Sort. Now Bubble sort is a sorting algorithm you would probably never use in real life as there are more optimised ways to sort, this is just for learning purpose. In the end we will also build a fun bubble sort visualiser in HTML, CSS, JavaScript.

What is bubble sort?

Bubble Sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed.

The algorithm is pretty simple: compare two items in an array that are next to each other. If they're out of order (that is, the larger one comes first in the array) swap them. Then move forward one index, compare again, swap if needed, and continue to the next item in the array.

Once we've reached the end of the array, if we've swapped anything in the previous run through, the array could still be out of order, so we have to pass through again. Once we run through the whole array with no swaps, the array is sorted!

Lets understand with a small example


[1, 5, 4, 2, 3]

Are 1 and 5 out of order? No.
Are 5 and 4 out of order? Yes. Swap.

[1, 4, 5, 2, 3]

Are 5 and 2 out of order? Yes. Swap.

[1, 4, 2, 5, 3]

Are 5 and 3 out of order? Yes. Swap.

[1, 4, 2, 3, 5]

End of the array, did we swap anything? Yes. Loop again.

Are 1 and 4 out of order? No.
Are 4 and 2 out of order? Yes. Swap.

[1, 2, 4, 3, 5]

Are 4 and 3 out of order? Yes. Swap.

[1, 2, 3, 4, 5]

Are 4 and 5 out of order? No.
End of the array, did we swap anything? Yes. Loop again.

Are 1 and 2 out of order? No.
Are 2 and 3 out of order? No.
Are 3 and 4 out of order? No.
Are 4 and 5 out of order? No.
End of the array, did we swap anything? No. List is sorted.

Eventually, on your first run through, you will find the biggest number and will continue swapping with it until it reaches the last element in the array (like we did with 5 in our example.) This is why it's called bubble sort: the biggest elements bubble to the last spots.

Thinking about this for a second, that means at the end of the iteration we're guaranteed to have the biggest element at the last spot. At the end of our first iteration above, 5 is the last element in the array. That means the last element in the array is definitely at its correct spot. That part of the array is sorted.

So, on our second run through of the array, we technically don't need to ask Are 4 and 5 out of order? No. because know ahead of time that 5 is going to be bigger no matter what. So we can check one less element each iteration because we know at the end of each iteration we have one more guaranteed element to be in its correct. At the end of the second iteration we'll have 4 in its correct place, then 3, then 2, etc.

Big O

So what is the computational complexity of this algorithm? Let's talk worst case, best case, and average case.

Worst Case

What is the absolute worst case scenario? It'd be a backwards sorted list.

It would have to run all comparisons and always swap. Assuming we did the optimised version above, that'd be 4 comparisons and swaps on the first go-around, then 3, then 2, then 1, totalling 10 comparisons and swaps. This will grow exponentially as the list gets bigger. This would be O(n²).

Worst Case: O(n²)

Best Case

What is the absolute best, ideal case for this algorithm? A sorted list.

It would run through the list once, comparing each element to its neighbour once, not swap anything, and be done. In our list of five that would be four comparisons and no swaps. Best case here is O(n) since the best case is just one run through so it'd grow linearly.

Best Case: O(n)

Average Case

What is the average case ? You can think of average case as "what happens if we through a randomly sorted list at this".

For our bubble sort, it'd be like the one we did above: some numbers in order, some not. What happens if we through 10 at it versus 1000. The amount of comparisons and swaps would grow exponentially. As such, we'd say it's O(n²) as well.

Average Case: O(n²)

spatial complexity `O(1)`

What about the spatial complexity? In our case, we're operating on the array itself and not creating anything else in memory, so the spatial complexity of this is O(1) since it'd never grow.

Because we are operating on the array itself, we'd say this sort is destructive. What if you needed to keep the original array in addition to the sorted one? You couldn't use this sorting method or you'd have to pre-emptively make a copy. Other sorting algorithms are non-destructive.

Is this sorting algorithm stable?

To be considered a stable sort, the sort must guarantee that if two things are equal that that they stay in that same order. For example, if we have an array of users that looks like this: [{name: "Sarah"}, {name: "Shirley"}, {name: "Scott"}] and we're sorting by state, we'd have to guarantee that Shirley comes before Scott for the sort to be considered stable.

Sometimes this is important to you, sometimes you don't care. So is bubble sort stable? Yes, it'll guarantee that equivalent items come back in the order they were in.

Bubble Sort Implemented in JavaScript

There are a coupe of ways we can implement bubble sort in javascript, we will look at two of them today.

Using do..while


const bubbleSort = (nums) = {
  let swapped = false;

  do {
    swapped = false;

    for (let i = 0; i < nums.length; i++) {
      if (nums[i] > nums[i + 1]) {
        let temp = nums[i];
        nums[i] = nums[i + 1];
        nums[i + 1] = temp;
        swapped = true;
      }
    }
  } while (swapped);

}

const nums = [10, 5, 3, 8, 2, 6, 4, 7, 9, 1];
const sortedNums = bubbleSort(nums);
console.log(sortedNums === [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

Using for loops



 const bubbleSort = (arr) => {
    
 for(var i = 0; i < arr.length; i++){
    
   // Last i elements are already in place 
   for(var j = 0; j < ( arr.length - i -1 ); j++){
      
     // Checking if the item at present iteration
     // is greater than the next iteration
     if(arr[j] > arr[j+1]){
        
       // If the condition is true then swap them
       var temp = arr[j]
       arr[j] = arr[j + 1]
       arr[j+1] = temp
     }
   }
 }
 // Return the sorted array
 return arr
}

Implementing a bubble sort visualiser with html, css and JavaScript.

Lets add the markup in out html file and then add css

html


<p class="header">Bubble Sort</p>

<div id="array"></div>

css


* {
  margin: 0px;
  padding: 0px;
  box-sizing: border-box;
}

.header {
  font-size: 20px;
  text-align: center;
}

#array {
  background-color: white;
  height: 413px;
  width: 598px;
  margin: auto;
  position: relative;
  margin-top: 64px;
}

.block {
  width: 28px;
  background-color: #fafa87;
  position: absolute;
  bottom: 0px;
  transition: 0.2s all ease;
}

.block_id {
  position: absolute;
  color: black;
  margin-top: -20px;
  width: 100%;
  text-align: center;
}

javascript


const container = document.getElementById("array");

// Function to generate the array of blocks
const generatearray = () => {
  for (let i = 0; i < 20; i++) {
    // Return a value from 1 to 100 (both inclusive)
    let value = Math.ceil(Math.random() * 100);

    // Creating element div
    let array_ele = document.createElement("div");

    // Adding class 'block' to div
    array_ele.classList.add("block");

    // Adding style to div
    array_ele.style.height = `${value * 3}px`;
    array_ele.style.transform = `translate(${i * 30}px)`;

    // Creating label element for displaying
    // size of particular block
    let array_ele_label = document.createElement("label");
    array_ele_label.classList.add("block_id");
    array_ele_label.innerText = value;

    // Appending created elements to index.html
    array_ele.appendChild(array_ele_label);
    container.appendChild(array_ele);
  }
};

// Promise to swap two blocks
const swap = (element1, element2) => {
  return new Promise((resolve) => {
    // For exchanging styles of two blocks
    let temp = element1.style.transform;
    element1.style.transform = element2.style.transform;
    element2.style.transform = temp;

    window.requestAnimationFrame(function () {
      // For waiting for .25 sec
      setTimeout(() => {
        container.insertBefore(element2, element1);
        resolve();
      }, 500);
    });
  });
};

// Asynchronous BubbleSort function
const BubbleSort = async (delay = 500) => {
  let blocks = document.querySelectorAll(".block");

  // BubbleSort Algorithm
  for (let i = 0; i < blocks.length; i += 1) {
    for (let j = 0; j < blocks.length - i - 1; j += 1) {
      // To change background-color of the
      // blocks to be compared
      blocks[j].style.backgroundColor = "#FF4949";
      blocks[j + 1].style.backgroundColor = "#FF4949";

      // To wait for .1 sec
      await new Promise((resolve) =>
        setTimeout(() => {
          resolve();
        }, delay)
      );

      let value1 = Number(blocks[j].childNodes[0].innerHTML);
      let value2 = Number(blocks[j + 1].childNodes[0].innerHTML);

      // To compare value of two blocks
      if (value1 > value2) {
        await swap(blocks[j], blocks[j + 1]);
        blocks = document.querySelectorAll(".block");
      }

      // Changing the color to the previous one
      blocks[j].style.backgroundColor = "#fafa87";
      blocks[j + 1].style.backgroundColor = "#fafa87";
    }

    //changing the color of greatest element
    //found in the above traversal
    blocks[blocks.length - i - 1].style.backgroundColor = "#13CE66";
  }
};

// Calling generatearray function
generatearray();

// Calling BubbleSort function
BubbleSort();