JavaScript Sorting Algorithms: Bubble Sort

#algorithms #javascript #sort

You can read more posts on programming and tech on my blog. This series will be updated as soon as I catch some free time :)

Introduction

So I have this thing on my blog called the JavaScript Sorting Algorithm series. This series of posts will try to explain and implement different sorting algorithms in our favorite scripting language - JS of course! And we will start our 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:

The algorithm will compare two adjacent elements. For example a and b.
The algorithm will swap them if they are out of order by checking whether a is less than b
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.
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].
The algorithm is vizualized using visualgo.

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(n2) 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 my blog for more tech articles.

DEV Community