Everything You Need to Know About Bubble Sort 🫧

Hey dev community! 👋🏻

I'm Seif, a software engineer with 4 years of experience specializing in Node.js, JavaScript and MongoDB. Today, I chose to start a new series that teaches you computer science algorithms for learning and interview preparation. In this article, I'm going to teach you the absolute, most basic sorting algorithm: Bubble Sort.

What is Bubble Sort?

Bubble Sort is a fundamental sorting algorithm that works by repeatedly stepping through a list, comparing adjacent elements and swapping them if they are in the wrong order. The algorithm gets its name because smaller or larger elements bubble to the top (the end of the list) with each pass. Think of it like gas bubbles rising in a liquid!

How it works in detail

Bubble Sort works by using nested loops to iterate through an array. It can sort items in ascending or descending order. For now, let's focus on sorting items in ascending order.

1. Start at the beginning of the array. Compare the first two elements (at index 0 and index 1).
2. If the first element is greater than the second element, swap them. If not, leave them as they are.
3. Move to the next pair of elements (at index 1 and index 2) and repeat the comparison.
4. Continue this until you reach the end of the array. By the end of the first pass, the largest element will have migrated to the last position.
5. Repeat the entire process for the remaining unsorted elements. Each pass places the next largest element into its correct final position.

Complexity

Bubble sort is rarely chosen for production use because it is slow. On average and in the worst-case scenario (when the array is reversed), its time complexity is quadratic. In the best case, it can achieve linear time complexity. Also, because it sorts in-place, its space complexity is constant. Perfecto 👌

Example implementation

Let's design a modern JavaScript implementation of this algorithm. We will focus on sorting numbers, even though the algorithm can be used to sort other data types, such as alphabetizing strings. I also used validation checks like Array.isArray() to prevent unexpected crashes if a developer accidentally passes a non-array arg.

function bubbleSort(arr) {
  if (!Array.isArray(arr)) {
    throw new TypeError("Input must be a valid array.");
  }

  // Validation
  if (!arr.every(Number.isFinite)) {
    throw new TypeError("Array must contain numbers only.");
  }

  // Clone the array for immutability
  const sorted = [...arr];
  const n = sorted.length;

  for (let i = 0; i < n - 1; i++) {
    let swapped = false;

    for (let j = 0; j < n - i - 1; j++) {
      const current = sorted[j];
      const next = sorted[j + 1];

      // Compare and swap
      if (current > next) {
        [sorted[j], sorted[j + 1]] = [next, current];
        swapped = true;
      }
    }

    if (!swapped) {
      break;
    }
  }

  return sorted;
}

We use arr.every(Number.isFinite) upfront instead of validating numbers inside the nested loops for resource efficiency and preventing wasted work (if an array contains 1000 elements and the very last element is a string, an in-loop check will waste time sorting the first 999 items before finally crashing).

Example use

Now, we are ready to test our function. Let's use it to sort this array: [5, 1, 4, 2].

• Pass 1:
  • Compare 5 and 1. 5 > 1, so swap. Now the array is: [1, 5, 4, 2]
  • Compare 5 and 4. 5 > 4, so swap. Now the array is: [1, 4, 5, 2]
  • Compare 5 and 2. 5 > 2, so swap. Now the array is: [1, 4, 2, 5]
• Pass 2:
  • Compare 1 and 4. 1 < 4, so no swap. Now the array is: [1, 4, 2, 5]
  • Compare 4 and 2. 4 > 2, so swap. Now the array is: [1, 2, 4, 5]
• Pass 3:
  • Compare 1 and 2. 1 < 2, so no swap. Now the array is: [1, 2, 4, 5]

We just did it! 🎉 Our final sorted array is: [1, 2, 4, 5]

Pros and cons of Bubble Sort

Bubble Sort is a great algorithm for learning, but it has many disadvantages, that's why we should avoid it in production.

Advantages

• Simplicity: Incredibly easy to understand and write.
• No Extra Memory: Generally, it performs sorting in-place, but because our implementation above clones the array to ensure immutability, its space complexity is linear.
• Detects Sorted Lists quickly: With optimization, it stops instantly on a sorted list.

Disadvantages

• Bad Efficiency: A quadratic time complexity makes it slower for large datasets compared to Merge Sort or Quick Sort.
• Excessive Swapping: It writes to memory frequently due to constant swapping, which can be mechanically costly.

That is my wrap on Bubble Sort! While it is rarely used in production code, mastering it gives you foundational algorithmic thinking!

See you in the next article, where we will transition from sorting data to finding it fast using Binary Search.

Thanks for reading! 🌟