Understanding Bubble Sort Algorithm in Javascript.

Welcome to the very first article of the sorting algorithm series, where we will be looking at different sorting algorithms.

Prerequisites: BIG O NOTATION.
if this is your first time to come across the term "BIG O NOTATION",I recommend you to head over to this article BIG O NOTATION and get accustomed to it first as it is important to learn how the algorithm performs in terms of time and space complexity.

Alright, let's now begin.

A quick definition of bubble sort is that, it bubbles up at the top the largest element inside an array. by bubbling up, I mean that It moves that value or an element inside the array at the end.

let'say we have an array with [1,3,8,5,7], after the first loop the array will end up like this [1,3,5,7,8] and as you can see the largest element which is 8 in this context has been bubbled up at the top.

By that we know that the largest element has been found and placed in a safe place where we don't need to touch it again, and then bubble sort repeats this process until all the largest element are placed at the end of the array.

I know this will be clear once we start to implement it, so here is the pseudo code:

• Start looping from the end of the array with a variable called i that goes down until the beginning.
• initiate an inner loop inside the outer loop with a variable called j, it loops from the beginning of the array until i - 1.
• compare and check if arr[j] is greater than the next element which is arr[j+1]. if that's the case Swap those value. Swapping will allow us to move the largest element till it reaches the top of the array.
• Finally after all this process, we will simply have to return the array,And put in mind that we will use the same array passed in as an argument without initiating a new one.

const bubbleSort = (arr) => {
  // this is a function which will help us in swapping 2 elements
  const swap = (arr, i, j) => [arr[i], arr[j]] = [arr[j], arr[i]];

  // start looping from the end of the array
  // this will help us in keeping track of the already sorted item so that we don't check it again.
  for(let i = arr.length; i > 0; i--){
    // start looping from the beginning of the array until i - 1.
    // this loop starts from the beginning and stops right in front of the current i.
    // as I said up earlier, there is no need to check against some already sorted items.
    for(let j = 0; j < i - 1; j++){
      // compare the current element to the next one, and swap
      // it swappes only if the current element is greater than the next element.
      if(arr[j] > arr[j+1]) swap(arr, j, j + 1);
    }
  }
  // return our sorted arr.
  return arr;
}

The very basic thing to pay attention to in this implementation and all other comparison sorting algorithm is the looping process, once you understand it you can implement it by your own.

We can also optimize it by keeping track of swaps process for the sake of time complexity and only swap when the if condition is valid, we can achieve that by initializing a noSwap variable. let's take a look at its implementation below

function bubbleSort(arr){
  let noSwaps; // noSwaps variable initialization.
  for(let i = arr.length; i > 0; i--){
    noSwaps = true; // setting it to true at first, by assuming there is no swaps for every time we loop through the values.
    for(let j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
        let temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
        noSwaps=false; // if we make a swap, set it to false so that we keep comparing the elements.
      }
    }
    // if we don't make any swaps just break out of the loop.
    if(noSwaps) break;
  }
  return arr;
}

Before we wrap up, we also need to talk about BIG O NOTATION of bubble sort.

in general for worst case scenarios which is what we should care on because it is hard to know the state of your data structure, its time complexity is quadratic O(n^2).

for the average case scenarios, its time complexity is also quadratic O(n^2).

for the best case scenarios which applies to the nearly sorted array, the time complexity is linear O(n).

the space complexity of bubble sort is constant O(1), as we don't define many variable to consume the memory.

And that's everything about bubble sort fellow developers, and next time we will look into selection sort which is basically the opposite of bubble sort.

so keep your eye open for that next article and feel free to ask me any question on twitter as Me on Twitter

Dios te bendiga.