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 algorithm: Bubble Sort.

What is Bubble Sort?

Bubble Sort is a fundamental sorting algorithm. It 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.

Example implementation

Let's design a modern JavaScript implementation of the Bubble Sort 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.

// Implementation to sort numbers in ascending order
function bubbleSort(arr) {
    if (!Array.isArray(arr)) {
        throw new TypeError("Input must be a valid array.");
    }

    // 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];

            if (!Number.isFinite(current) || !Number.isFinite(next)) {
                throw new TypeError("Array must contain numbers only.");
            }

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

        if (!swapped) {
            break;
        }
    }

    return sorted;
}

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, explain, and write.
• No Extra Memory: Performs sorting entirely in-place.
• Detects Sorted Lists quickly: With optimization, it stops instantly on a sorted list.

Disadvantages

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

Let's talk!

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

Now, I want to hear from you: Did you know about JavaScript's Number.isFinite() trick to elegantly stop NaN, Infinity, and -Infinity from breaking number comparisons?

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

Thanks for reading! 🌟