Bubble Sort Algorithm

Introduction to Bubble Sort

Bubble Sort is a simple and intuitive sorting algorithm used to arrange elements of an array in either ascending or descending order. It repeatedly compares adjacent elements and swaps them if they are in the wrong order. This process continues until the array is fully sorted.

Although Bubble Sort is easy to implement, it's not very efficient for large datasets due to its time complexity of (O(n^2)), where (n) is the number of elements in the array.

How Bubble Sort Works

The algorithm works by "bubbling" the largest unsorted element to the end of the array in each iteration. Here's a step-by-step explanation:

1. Start from the first element of the array.
2. Compare the current element with the next element.
3. If the current element is greater than the next element (for ascending order), swap them.
4. Move to the next element and repeat the process until the end of the array.
5. Repeat the process for all elements, reducing the range of comparisons in each pass, since the last element(s) are already sorted.

Pseudo Code for Bubble Sort

function bubbleSort(arr):
    n = length of arr
    for i from 0 to n-1:
        for j from 0 to n-i-1:
            if arr[j] > arr[j+1]:
                swap arr[j] and arr[j+1]
    return arr

Flowchart

Below is a simple flowchart that represents the logic behind Bubble Sort:

JavaScript Code Example

Here’s how you can implement Bubble Sort in JavaScript:

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

    // Outer loop to traverse the array
    for (let i = 0; i < n - 1; i++) {

        // Inner loop for adjacent comparisons
        for (let j = 0; j < n - i - 1; j++) {

            // Compare adjacent elements
            if (arr[j] > arr[j + 1]) {
                // Swap if elements are in wrong order
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

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

Explanation of JavaScript Code:

1. Outer Loop (****i loop): This loop runs (n - 1) times, where (n) is the size of the array. After each iteration, the largest unsorted element bubbles to the rightmost position.
2. Inner Loop (****j loop): This loop compares adjacent elements and swaps them if they are in the wrong order. As the array gets sorted from the right, the number of comparisons decreases in each subsequent iteration.
3. Swapping: If the element at index j is greater than the element at index j + 1, they are swapped using a temporary variable temp.

Time Complexity of Bubble Sort

• Best case: (O(n)) - when the array is already sorted (we can add an optimization to break early if no swaps are needed).
• Worst case: (O(n^2)) - when the array is in reverse order.
• Average case: (O(n^2)) - generally, Bubble Sort requires a large number of comparisons and swaps even for moderate-sized arrays.

Space Complexity

Bubble Sort is an in-place sorting algorithm, meaning it only requires a constant amount of extra space, i.e., (O(1)).

Conclusion

Bubble Sort is a great algorithm for educational purposes and for understanding the basic concepts of sorting. However, its inefficiency in handling large datasets makes it less practical for real-world applications where more efficient sorting algorithms like Quick Sort or Merge Sort are preferred.

This article covers the basic explanation, pseudo code, flowchart, and JavaScript implementation of the Bubble Sort algorithm.