JavaScript Sorting Algorithms Explained: Bubble Sort

Welcome to the new series on this blog. This is part one of JavaScript Sorting Algorithms series: Bubble Sort.

Introduction

JavaScript Sorting Algorithms series will try to explain and implement different sorting algorithms in our favorite scripting language – JS of course! And we will start our JavaScript Sorting Algorithms journey with the easiest one – bubble sort.

Although the bubble sort algorithm compared to other sorting algorithms isn’t that efficient, and isn’t used anywhere in the real world, interviewers still commonly check for it during interviews. It is good to at least know how it works under the hood.

How does bubble sort (you can also find it under the alternate name sinking sort) work. The algorithm ‘bubbles’ large values (thus the name) to the top on each iteration of the algorithm. Then it compares adjacent elements between each other and swaps them if they are in the wrong order.

Pseudo code looks like this:

1. The algorithm will compare two adjacent elements. For example a and b.
2. The algorithm will swap them if they are out of order by checking whether a is less than b
3. The algorithm will repeat steps 1. and 2. until the end of the array is reached. At the end of iteration the largest number should be at the very end of the array.
4. The algorithm will then ignore the last item and repeat step 1, until all the elements are sorted

Let us visualize this algorithm using the inputs [15, 6, 4, 18, 7, 13, 1].

So, at first we compare every element with its adjacent elements (green elements). If the element is larger – it will be swapped, during each iteration the largest element will be stuck to the end (orange elements). This process repeats itself until all the elements are sorted.

Implementation

function bubbleSort(arr) {
    for(let i = arr.length; i > 0; i--) {
        for(let j = 0; j < i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }

    return arr;
}

bubbleSort([15, 6, 4, 18, 7, 13, 1]);

Every iteration we reduce the iterator by 1 (because the last element is already sorted!). if the element is bigger than its adjacent element, we will use the swapping mechanism [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] (a pretty cool ES6 concept to swap items in place without the need for a temporary variable).

Optimize it!

There is one specific scenario in which we can optimize the algorithm a bit.

If the array is almost sorted – needing to rearrange only an item or two, the algorithm still goes through all the loops, even though nothing is happening.

In order to fix this – we just need to check whether we made any swaps.

function bubbleSort(arr) {
  let swapHappened;
  for (let i = arr.length; i > 0; i--) {
    swapHappened = true;
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapHappened = false;
      }
    }
    if (swapHappened) {
      break;
    }
  }

  return arr;
}

bubbleSort([2, 4, 6, 5, 7, 9, 12]);

Big O complexity

The average Big O of bubble sort is O(n²) because we iterate twice through the whole array. We need to compare current element to every other element in the array.

Conclusion

That’s it! Bubble sort isn’t a very demanding algorithm to learn. We will post more sorting algorithms in the future. In the meantime, please check the blog for more tech articles.

Additionally, if you want to check up on other sorting algorithms you can do it here:

• The OpenCV Journey Part II: Canny Edge Detection
• JavaScript Sorting Algorithms Explained: Counting Sort
• JavaScript Sorting Algorithms Explained: Radix Sort
• JavaScript Sorting Algorithms Explained: Quick Sort
• JavaScript Sorting Algorithms Explained: Merge Sort
• JavaScript Sorting Algorithms Explained: Insertion Sort
• JavaScript Sorting Algorithms Explained: Selection Sort
• JavaScript Sorting Algorithms Explained: Bubble Sort