How To Do Bubble Sort in JavaScript

Sorting algorithms are fundamental to programming, and Bubble Sort is one of the simplest algorithms to understand and implement. In this blog post, we’ll discuss how to implement Bubble Sort in JavaScript, discuss its time and space complexities, and explore when it’s appropriate to use it.

What is Bubble Sort?

Bubble Sort is a comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until no swaps are needed, indicating that the list is sorted.

Below, you can see a visualization of how Bubble Sort works. Choose the length of your array in the box next to Array Size (Max 30) then click Generate Random Array to generate the numbers, then click Start Sorting.

Time Complexity of Bubble Sort

• Best Case: O(n)—When the array is already sorted, Bubble Sort only needs to make one pass through it, making it O(n).
• Average Case: O(n²) – On average, the algorithm compares each element with each other, resulting in quadratic complexity.
• Worst Case: O(n²) – In the worst-case scenario, where the array is in reverse order, Bubble Sort has to make the maximum number of swaps, resulting in O(n²).

Space Complexity of Bubble Sort

• Space Complexity: O(1) – Bubble Sort is an in-place sorting algorithm requiring a constant amount of extra memory, regardless of the input size.

Pseudocode for Bubble Sort

The pseudocode for Bubble Sort outlines the basic steps of the algorithm:

procedure bubbleSort(arr)
    n = length(arr)
    repeat
        swapped = false
        for i = 0 to n-2 do
            if arr[i] > arr[i+1] then
                swap(arr[i], arr[i+1])
                swapped = true
        n = n - 1
    until swapped = false

Step-by-Step Explanation:

• You iterate through the array multiple times.
• During each pass, adjacent elements are compared, and if they are out of order, they are swapped.
• This process is repeated until no swaps occur during a complete pass, meaning the array is fully sorted.

JavaScript Implementation of Bubble Sort

Here is how you can implement Bubble Sort in JavaScript:

function bubbleSort(arr) {
    let n = arr.length;
    let swapped;

    do {
        swapped = false;
        for (let i = 0; i < n - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                // Swap the elements
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                swapped = true;
            }
        }
        // Decrease the range of comparison for the next pass
        n--;
    } while (swapped);
    
    return arr;
}

// Example usage:
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log("Initial array:", arr);
console.log("Sorted array:", bubbleSort(arr));

Output

Initial array: [
  64, 34, 25, 12,
  22, 11, 90
]
Sorted array: [
  11, 12, 22, 25,
  34, 64, 90
]

Explanation:

• The function loops through the array, compares adjacent elements, and swaps them if needed.
• It uses a do-while loop, which ensures the process continues as long as swaps occur during a pass.
• With each iteration, the largest unsorted element “bubbles” to the correct position, and the size of the unsorted portion of the array decreases.

Pros and Cons of Using Bubble Sort

Pros:

1. Simplicity: Bubble Sort is one of the most accessible algorithms to understand and implement, making it a good learning tool for beginners.
2. In-Place Sorting: It uses O(1) additional space, meaning it doesn’t require any extra data structures.
3. Stability: Bubble Sort is a stable sorting algorithm that preserves the relative order of elements with equal keys.

Cons:

1. Inefficiency: Its time complexity of O(n²) makes it inefficient for large datasets compared to more advanced algorithms like QuickSort or MergeSort.
2. Not Practical: Bubble Sort is rarely used in real-world applications where large data needs to be sorted due to its poor average-case performance.
3. Many Comparisons: Even if the array is nearly sorted, Bubble Sort makes unnecessary comparisons unless optimized further.

When to Use Bubble Sort

While Bubble Sort is not typically used in production-level applications due to its inefficiency, it can be useful in the following situations:

1. Small Datasets: Bubble Sort’s simplicity can make it a reasonable option for working with very small arrays.
2. Teaching and Learning: Bubble Sort is excellent for understanding the basic principles of sorting and how comparison-based algorithms work.
3. Stability Requirement: If you need a stable sorting algorithm and performance isn’t a concern, Bubble Sort can be used since it maintains the relative order of equal elements.
4. Pre-Sorted Data: In cases where the data is nearly or entirely sorted, Bubble Sort’s best-case performance of O(n) makes it a reasonable choice.

Conclusion

Bubble Sort is one of the simplest sorting algorithms in terms of implementation and conceptual understanding. While it is unsuitable for large datasets due to its O(n²) time complexity, it can still be helpful in specific cases, such as small datasets or learning environments. If you’re working with larger datasets, consider using more efficient algorithms like Merge Sort or QuickSort.

Understanding Bubble Sort is an essential first step in grasping more complex algorithms, and with its straightforward implementation in JavaScript, it’s a great way to start learning about sorting algorithms.

Congratulations on reading to the end of this tutorial!

Read the following articles to learn how to implement Bubble Sort:

In Python – How to do Bubble Sort in Python

In C++ – How to Do Bubble Sort in C++

In Rust – How to do Bubble Sort in Rust

Have fun and happy researching!