Bubble Sort: The Most Basic yet Inefficient Friend

Chris shuffled a deck of cards to play a game and is now trying to sort them back in order.

However, his sorting method is a bit peculiar.

He holds only two cards starting from the far left and compares them. "Is the left one bigger? Swap." Then he moves one spot to the right and compares two cards again.

He repeats this process until the end, then goes back to the start and repeats it all over again.

"Chris, what are you doing? When will you finish sorting?"

This is Bubble Sort, the ancestor of sorting algorithms and the most inefficient sorting method.

1. Rising Like Bubbles?

The name "Bubble Sort" comes from the way data sorts itself, resembling "bubbles rising to the water's surface."

The principle is very simple.

"Inspect two adjacent elements, and if they are in the wrong order, swap them."

Every time you complete one full pass of this operation, the largest number moves to the very back of the array (the surface) and settles into its correct position.

Operational Process (Ascending Order Example: [5, 3, 8, 1])

Pass 1

Pass 2

Repeat this process for the number of data items, and the sort is complete.

2. Implementing in JavaScript

The most basic implementation method uses nested loops.

function bubbleSort(arr) {
  // Shrink the scope from the back (i is the end of the range to sort)
  for (let i = arr.length; i > 0; i--) {
    // Compare from the start up to i-1, pushing the "bubble" up
    for (let j = 0; j < i - 1; j++) {
      console.log(arr, arr[j], arr[j+1]); // Let's visualize the process

      if (arr[j] > arr[j + 1]) {
        // SWAP! Swap variables using destructuring assignment
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

bubbleSort([37, 45, 29, 8]);

3. Performance Analysis: Why is it Inefficient?

Let's analyze this code using Big-O notation.

If there are 10 items, it performs 100 operations. If there are 1,000 items, it performs 1 million operations. Performance degrades geometrically with even a slight increase in data. It ranks at the bottom among sorting algorithms.

4. Optimization: Reducing the Inefficiency

What if the data is already nearly sorted, like [1, 2, 3, 5, 4]?

The basic Bubble Sort stupidly continues to compare until the end, even though the sort is practically finished.

To prevent this, we can add a noSwaps variable. If "no swaps occurred" during a single pass, it means the sort is complete, so we can break out of the loop.

// ✅ Optimized Bubble Sort
function bubbleSortOptimized(arr) {
  let noSwaps;
  for (let i = arr.length; i > 0; i--) {
    noSwaps = true; // Assume it's sorted for now
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        noSwaps = false; // A swap happened, so we are not done yet
      }
    }
    if (noSwaps) break; // If no swaps, terminate!
  }
  return arr;
}

With this optimization, it shows amazing speed close to O(N) strictly for already sorted data. (Of course, it is still O(N^2) on average).

Key Takeaways

Bubble Sort was a method of pushing large numbers to the back.

Then, conversely, what about a method that finds the smallest number and brings it to the front? There is a friend whose comparison count is similar, but who drastically reduces the "Swap" count.

🔗 References