Bubble Up: The Simple Art of Sorting with Bubble Sort

Bubble Sort is one of the simplest sorting algorithms that compares adjacent elements in an array and swaps them if they are in the wrong order. The process repeats until the array is sorted. It’s called the “Bubble” sort because smaller elements gradually “bubble” to the top of the array, while larger elements sink to the bottom.

How Does It Work?

1. Compare the first two elements.
2. If the first element is greater than the second, swap them.
3. Move to the next pair of adjacent elements and repeat the process.
4. Continue the passes until the array is sorted.

Time Complexity: O(n²), where n is the number of elements.
Space Complexity: O(1), as it operates in place.

Example: Visualizing the Algorithm

Unsorted Array: [5, 3, 8, 4, 2]

1st pass:

• Compare 5 and 3, swap → [3, 5, 8, 4, 2]
• Compare 5 and 8, no swap → [3, 5, 8, 4, 2]
• Compare 8 and 4, swap → [3, 5, 4, 8, 2]
• Compare 8 and 2, swap → [3, 5, 4, 2, 8]

2nd pass:

• Compare 3 and 5, no swap → [3, 5, 4, 2, 8]
• Compare 5 and 4, swap → [3, 4, 5, 2, 8]
• Compare 5 and 2, swap → [3, 4, 2, 5, 8]

And the process continues until fully sorted: [2, 3, 4, 5, 8].

JavaScript Code Example

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

const unsortedArray = [5, 3, 8, 4, 2];
console.log(bubbleSort(unsortedArray)); 
// Output: [2, 3, 4, 5, 8]

Optimized Bubble Sort

You can optimize Bubble Sort by introducing a flag that checks if any swaps were made in a pass. If no swaps were made, the array is already sorted, and you can exit early.

function bubbleSortOptimized(arr) {
  let len = arr.length;
  let swapped;
  for (let i = 0; i < len; i++) {
    swapped = false;
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // Exit if no swaps were made
  }
  return arr;
}

const array = [5, 3, 8, 4, 2];
console.log(bubbleSortOptimized(array));
// Output: [2, 3, 4, 5, 8]

Pros and Cons of Bubble Sort

Pros:

• Simple and easy to understand.
• Requires no additional memory (in-place sorting).

Cons:

• Inefficient for large datasets (O(n²) time complexity).
• Better algorithms like Merge Sort or Quick Sort are usually preferred.

When to Use Bubble Sort?

Bubble Sort is best used for small datasets or educational purposes, where simplicity is more important than efficiency. In real-world applications, other sorting algorithms like Quick Sort or Merge Sort are typically better suited for performance-critical tasks.

Conclusion

Though Bubble Sort is not efficient for large datasets, it is a great introductory algorithm to understand how sorting works. By learning it, you build a foundation for understanding more complex sorting algorithms.