Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

Implementation in JavaScript

function bubbleSort(arr) {
    const n = arr.length;
    
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < n - i - 1; j++) {
            // Compare adjacent elements
            if(arr[j] > arr[j + 1]) {
                // Swap them if they are in wrong order
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

// Example usage
const arr = [64, 34, 25, 12, 22];
console.log(bubbleSort(arr)); // Output: [12, 22, 25, 34, 64]

Optimized Version

Here's an optimized version that stops early if the array is already sorted:

function bubbleSortOptimized(arr) {
    const n = arr.length;
    
    for(let i = 0; i < n; i++) {
        let swapped = false;
        
        for(let j = 0; j < n - i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        
        // If no swapping occurred, array is already sorted
        if(!swapped) break;
    }
    return arr;
}

Time Complexity

• Worst Case: O(n²) - when array is reverse sorted

• Average Case: O(n²)

• Best Case: O(n) - when array is already sorted (with optimized version)

Space Complexity

• O(1) - only a single additional memory space is needed for the swapping of elements

Where it's used

• When array size is small

• When simplicity of implementation is preferred over efficiency

• In educational contexts to teach sorting concepts