Bubble-sort

Cover image from: Unsplash - Kai Dahms

Intro

This is going to be a series about different sorting algorithms, some explanation and a quick demo with solution in JavaScript.

Bubble sort

First of all, let start with the most basic one - bubble sort.
The logic behind bubble sort is the following:

• starting from the beginning, compare two adjacent elements
• if the previous one is bigger than the following one, swap those two
• repeat until there is no element left in the array

This is just one iteration, which guarantees that the biggest element is at the end of the array.

• repeat this process for every element in the array

Complexity

As you may see, there are several different outcomes, and based on the number of the elements to compare, things quickly can get out of control.

Best case scenario: The elements are ordered > we will do O(n) comparisons.

Worst case scenario: The elements are reverse ordered > we will do O(n²) comparison. It does not look like a problem for 10 elements, but for 1000, there will be a lot of zero after that first leading one. :)

Average scenario: Sadly, the average scenario has the same time complexity as the worst one, which still will be O(n²).

Usage

I think bubble sort is not so problematic, because of its ease to understand. Use it wisely, and use it for small amount of elements. There is nothing wrong with it - up to a minimal amount of elements.

Implementation

Of course, there are a lot of way to implement this, but I will leave mine here for anyone who is interested in. I will link the GitHub repo for this as well.

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

  return array;
}

Some sneak peak:

• the easiest way to swap two variables is [a, b] = [b, a] > you do not need a tmp one then
• you do not have to loop the array until the end every iteration > if the greatest is already at the end (and the nth greatest .. so on) leave that alone

Reference

Repo