Bubble Sort in JavaScript - Complete Guide

Introduction

Bubble Sort is a simple comparison-based sorting algorithm that takes O(n²) time complexity. Despite not being the most efficient sorting algorithm, it's excellent for educational purposes and understanding the fundamentals of sorting algorithms.

Key Characteristics

Simple to understand and implement
Stable sorting algorithm (maintains relative order of equal elements)
In-place sorting (requires only O(1) extra space)
Comparison-based algorithm

How Bubble Sort Works

Bubble Sort works by making multiple passes through the array:

First Pass: Move the largest element to the last position (its final position)
Second Pass: Move the second largest element to the second last position
Continue: Keep doing this until all elements are in their correct positions

Core Concept

Compare adjacent elements
Swap them if they are out of order (left element > right element)
The largest element "bubbles up" to its correct position in each pass

Step-by-Step Example

Let's trace through sorting the array [8, 2, 10, 7]:

Pass 1: Moving the largest element (10) to the end

Initial: [8, 2, 10, 7]
 
Step 1: Compare 8 and 2
8 > 2, so swap → [2, 8, 10, 7]
 
Step 2: Compare 8 and 10  
8 < 10, no swap → [2, 8, 10, 7]
 
Step 3: Compare 10 and 7
10 > 7, so swap → [2, 8, 7, 10]
 
After Pass 1: [2, 8, 7, 10] ✓ (10 is in final position)

Pass 2: Moving the second largest element (8) to second last position

Start: [2, 8, 7, 10]
 
Step 1: Compare 2 and 8
2 < 8, no swap → [2, 8, 7, 10]
 
Step 2: Compare 8 and 7
8 > 7, so swap → [2, 7, 8, 10]
 
After Pass 2: [2, 7, 8, 10] ✓ (8 and 10 are in final positions)

Pass 3: Final comparison

Start: [2, 7, 8, 10]
 
Step 1: Compare 2 and 7
2 < 7, no swap → [2, 7, 8, 10]
 
Final Result: [2, 7, 8, 10] ✓ (All elements sorted)

Basic Implementation

Here's the basic implementation of Bubble Sort in JavaScript:

function bubbleSort(arr) {
    const n = arr.length;
    
    // Outer loop for number of passes (n-1 passes needed)
    for (let i = 0; i < n - 1; i++) {
        // Inner loop for comparisons in each pass
        // After each pass, one more element is in final position
        for (let j = 0; j < n - i - 1; j++) {
            // Compare adjacent elements
            if (arr[j] > arr[j + 1]) {
                // Swap if they are out of order
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    
    return arr;
}
 
// Example usage
const numbers = [8, 2, 10, 7];
console.log('Original array:', numbers);
console.log('Sorted array:', bubbleSort([...numbers])); // Use spread to avoid modifying original
// Output: [2, 7, 8, 10]

Understanding the Loop Structure

// For n = 4 elements, we need 3 passes
// Pass 1: i = 0, j runs 3 times (0, 1, 2)
// Pass 2: i = 1, j runs 2 times (0, 1) 
// Pass 3: i = 2, j runs 1 time (0)
 
// General pattern:
// Outer loop: i from 0 to n-2 (n-1 iterations)
// Inner loop: j from 0 to n-i-2 (n-i-1 iterations)

Dry Run Example

Let's trace through the algorithm execution with detailed variable tracking:

function bubbleSortWithTrace(arr) {
    const n = arr.length;
    console.log('Starting Bubble Sort with array:', arr);
    
    for (let i = 0; i < n - 1; i++) {
        console.log(`\n--- Pass ${i + 1} (i = ${i}) ---`);
        let swapped = false;
        
        for (let j = 0; j < n - i - 1; j++) {
            console.log(`Comparing arr[${j}] = ${arr[j]} with arr[${j + 1}] = ${arr[j + 1]}`);
            
            if (arr[j] > arr[j + 1]) {
                // Swap elements
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
                console.log(`  → Swapped! Array is now: [${arr.join(', ')}]`);
            } else {
                console.log(`  → No swap needed`);
            }
        }
        
        console.log(`End of Pass ${i + 1}: [${arr.join(', ')}]`);
        if (!swapped) {
            console.log('No swaps made - array is sorted!');
            break;
        }
    }
    
    return arr;
}
 
// Example execution
const testArray = [64, 34, 25, 12, 22, 11, 90];
bubbleSortWithTrace([...testArray]);

Expected Output:

Starting Bubble Sort with array: [64, 34, 25, 12, 22, 11, 90]

--- Pass 1 (i = 0) ---
Comparing arr[0] = 64 with arr[1] = 34
  → Swapped! Array is now: [34, 64, 25, 12, 22, 11, 90]
Comparing arr[1] = 64 with arr[2] = 25
  → Swapped! Array is now: [34, 25, 64, 12, 22, 11, 90]
...
End of Pass 1: [34, 25, 12, 22, 11, 64, 90]

--- Pass 2 (i = 1) ---
...

Time Complexity Analysis

Detailed Analysis

// For an array of size n:
// Pass 1: (n-1) comparisons
// Pass 2: (n-2) comparisons  
// Pass 3: (n-3) comparisons
// ...
// Pass (n-1): 1 comparison
 
// Total comparisons = (n-1) + (n-2) + (n-3) + ... + 1
// This is the sum of first (n-1) natural numbers
// Sum = (n-1) × n / 2 = (n² - n) / 2
 
// Therefore: Time Complexity = Θ(n²)

Complexity in Different Cases

Case	Time Complexity	Description
Best Case	O(n)	Array is already sorted (with optimization)
Average Case	O(n²)	Elements are in random order
Worst Case	O(n²)	Array is sorted in reverse order

Example of Worst Case

// Worst case: Reverse sorted array
const worstCase = [5, 4, 3, 2, 1];
 
// This requires maximum number of swaps:
// Pass 1: 4 swaps → [4, 3, 2, 1, 5]
// Pass 2: 3 swaps → [3, 2, 1, 4, 5]  
// Pass 3: 2 swaps → [2, 1, 3, 4, 5]
// Pass 4: 1 swap  → [1, 2, 3, 4, 5]
// Total: 10 swaps = n(n-1)/2 swaps

Optimized Implementation

The basic implementation always runs in O(n²) time, even for sorted arrays. We can optimize it to detect when the array becomes sorted:

function optimizedBubbleSort(arr) {
    const n = arr.length;
    
    for (let i = 0; i < n - 1; i++) {
        let swapped = false; // Flag to track if any swap occurred
        
        // Last i elements are already in place
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap elements
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true; // Mark that a swap occurred
            }
        }
        
        // If no swapping occurred, array is sorted
        if (!swapped) {
            console.log(`Array sorted after ${i + 1} passes`);
            break;
        }
    }
    
    return arr;
}
 
// Test with already sorted array
const sortedArray = [1, 2, 3, 4, 5];
console.log('Sorting already sorted array:');
optimizedBubbleSort([...sortedArray]);
// Output: "Array sorted after 1 passes"
 
// Test with reverse sorted array  
const reverseArray = [5, 4, 3, 2, 1];
console.log('Sorting reverse sorted array:');
optimizedBubbleSort([...reverseArray]);
// This will take all 4 passes

Benefits of Optimization

Best case becomes O(n) instead of O(n²)
Early termination when array becomes sorted
Same worst-case complexity O(n²)

Stability in Bubble Sort

Bubble Sort is a stable sorting algorithm, meaning it maintains the relative order of equal elements.

Why Bubble Sort is Stable

// Bubble sort only swaps when arr[j] > arr[j+1]
// It never swaps equal elements, preserving their order
 
function demonstrateStability() {
    // Array of objects with same values but different identifiers
    const students = [
        { name: 'Alice', grade: 85, id: 'A' },
        { name: 'Bob', grade: 90, id: 'B' },
        { name: 'Charlie', grade: 85, id: 'C' },
        { name: 'David', grade: 90, id: 'D' }
    ];
    
    console.log('Original order:', students.map(s => s.id).join(', '));
    
    // Sort by grade using bubble sort logic
    bubbleSortObjects(students, 'grade');
    
    console.log('After sorting by grade:', students.map(s => s.id).join(', '));
    // Output: A, C, B, D (Alice before Charlie, Bob before David)
    // This shows stability - equal elements maintain original order
}
 
function bubbleSortObjects(arr, key) {
    const n = arr.length;
    
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            // Only swap if strictly greater (not equal)
            if (arr[j][key] > arr[j + 1][key]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    
    return arr;
}
 
demonstrateStability();

Stability Example with Numbers

// Even with simple numbers, we can demonstrate stability
// by tracking original positions
 
function stableBubbleSort(arr) {
    // Add original index to track stability
    const indexedArray = arr.map((value, index) => ({ value, originalIndex: index }));
    
    const n = indexedArray.length;
    
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            // Compare values, use original index as tiebreaker
            if (indexedArray[j].value > indexedArray[j + 1].value) {
                [indexedArray[j], indexedArray[j + 1]] = [indexedArray[j + 1], indexedArray[j]];
            }
        }
    }
    
    return indexedArray.map(item => item.value);
}
 
// Test stability
const testArray = [3, 1, 3, 2, 3];
console.log('Original:', testArray);
console.log('Sorted:', stableBubbleSort([...testArray]));
// Equal elements maintain their relative positions

Space Complexity

Bubble Sort has O(1) auxiliary space complexity:

function bubbleSort(arr) {
    const n = arr.length;
    
    // Only using a constant amount of extra variables
    // No additional arrays or data structures needed
    
    for (let i = 0; i < n - 1; i++) {        // O(1) space for i
        let swapped = false;                  // O(1) space for swapped
        
        for (let j = 0; j < n - i - 1; j++) { // O(1) space for j
            if (arr[j] > arr[j + 1]) {
                // Swapping uses no extra space (in-place)
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        
        if (!swapped) break;
    }
    
    return arr;
}
 
// Total auxiliary space: O(1)
// The algorithm sorts in-place, modifying the original array

Practical Examples

1. Sorting Different Data Types

// Sorting strings
function sortStrings() {
    const fruits = ['banana', 'apple', 'orange', 'grape'];
    
    function bubbleSortStrings(arr) {
        const n = arr.length;
        
        for (let i = 0; i < n - 1; i++) {
            let swapped = false;
            
            for (let j = 0; j < n - i - 1; j++) {
                // Use localeCompare for proper string comparison
                if (arr[j].localeCompare(arr[j + 1]) > 0) {
                    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                    swapped = true;
                }
            }
            
            if (!swapped) break;
        }
        
        return arr;
    }
    
    console.log('Original fruits:', fruits);
    console.log('Sorted fruits:', bubbleSortStrings([...fruits]));
}
 
sortStrings();

2. Sorting Objects by Multiple Criteria

function sortEmployees() {
    const employees = [
        { name: 'John', department: 'IT', salary: 60000 },
        { name: 'Alice', department: 'HR', salary: 55000 },
        { name: 'Bob', department: 'IT', salary: 65000 },
        { name: 'Carol', department: 'HR', salary: 55000 }
    ];
    
    function bubbleSortEmployees(arr, primaryKey, secondaryKey) {
        const n = arr.length;
        
        for (let i = 0; i < n - 1; i++) {
            let swapped = false;
            
            for (let j = 0; j < n - i - 1; j++) {
                let shouldSwap = false;
                
                // Primary comparison
                if (arr[j][primaryKey] > arr[j + 1][primaryKey]) {
                    shouldSwap = true;
                } else if (arr[j][primaryKey] === arr[j + 1][primaryKey]) {
                    // Secondary comparison for equal primary values
                    if (arr[j][secondaryKey] > arr[j + 1][secondaryKey]) {
                        shouldSwap = true;
                    }
                }
                
                if (shouldSwap) {
                    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                    swapped = true;
                }
            }
            
            if (!swapped) break;
        }
        
        return arr;
    }
    
    console.log('Original employees:', employees);
    console.log('Sorted by department, then salary:', 
                bubbleSortEmployees([...employees], 'department', 'salary'));
}
 
sortEmployees();

3. Custom Comparison Function

function customBubbleSort(arr, compareFunction) {
    const n = arr.length;
    
    for (let i = 0; i < n - 1; i++) {
        let swapped = false;
        
        for (let j = 0; j < n - i - 1; j++) {
            // Use custom comparison function
            if (compareFunction(arr[j], arr[j + 1]) > 0) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        
        if (!swapped) break;
    }
    
    return arr;
}
 
// Example: Sort by absolute value
const numbers = [-5, 3, -1, 4, -2];
const sortedByAbs = customBubbleSort([...numbers], (a, b) => Math.abs(a) - Math.abs(b));
console.log('Sorted by absolute value:', sortedByAbs);
// Output: [-1, -2, 3, 4, -5]
 
// Example: Sort strings by length
const words = ['javascript', 'html', 'css', 'react'];
const sortedByLength = customBubbleSort([...words], (a, b) => a.length - b.length);
console.log('Sorted by length:', sortedByLength);
// Output: ['css', 'html', 'react', 'javascript']

When to Use Bubble Sort

Good Use Cases ✅

Educational purposes - Easy to understand and implement
Small datasets (< 50 elements) where simplicity matters
Nearly sorted data with optimization (O(n) best case)
When stability is required and simplicity is preferred
Memory-constrained environments (O(1) space complexity)

Avoid Bubble Sort ❌

Large datasets (> 100 elements) - O(n²) becomes too slow
Performance-critical applications - Use QuickSort, MergeSort, or built-in sort
Production systems - JavaScript's built-in sort is much faster

Performance Comparison

function performanceTest() {
    const sizes = [100, 500, 1000, 2000];
    
    sizes.forEach(size => {
        // Generate random array
        const arr = Array.from({ length: size }, () => Math.floor(Math.random() * 1000));
        
        // Test Bubble Sort
        const bubbleStart = performance.now();
        bubbleSort([...arr]);
        const bubbleTime = performance.now() - bubbleStart;
        
        // Test Built-in Sort
        const builtinStart = performance.now();
        [...arr].sort((a, b) => a - b);
        const builtinTime = performance.now() - builtinStart;
        
        console.log(`Size ${size}:`);
        console.log(`  Bubble Sort: ${bubbleTime.toFixed(2)}ms`);
        console.log(`  Built-in Sort: ${builtinTime.toFixed(2)}ms`);
        console.log(`  Ratio: ${(bubbleTime / builtinTime).toFixed(1)}x slower\n`);
    });
}
 
// performanceTest(); // Uncomment to run performance test

Comparison with Other Algorithms

Algorithm	Time Complexity	Space	Stable	Best Use Case
Bubble Sort	O(n²)	O(1)	Yes	Education, small arrays
Selection Sort	O(n²)	O(1)	No	Small arrays, minimal swaps
Insertion Sort	O(n²)	O(1)	Yes	Small/nearly sorted arrays
Merge Sort	O(n log n)	O(n)	Yes	Large arrays, stability needed
Quick Sort	O(n log n)	O(log n)	No	Large arrays, average case
JavaScript sort()	O(n log n)	O(log n)	Yes	Production use

Complete Working Examples

Example 1: Interactive Bubble Sort Visualizer

class BubbleSortVisualizer {
    constructor(array) {
        this.array = [...array];
        this.originalArray = [...array];
        this.steps = [];
        this.currentStep = 0;
    }
    
    sort() {
        const arr = [...this.array];
        const n = arr.length;
        
        for (let i = 0; i < n - 1; i++) {
            let swapped = false;
            
            for (let j = 0; j < n - i - 1; j++) {
                // Record comparison step
                this.steps.push({
                    type: 'compare',
                    indices: [j, j + 1],
                    array: [...arr],
                    pass: i + 1
                });
                
                if (arr[j] > arr[j + 1]) {
                    // Record swap step
                    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                    swapped = true;
                    
                    this.steps.push({
                        type: 'swap',
                        indices: [j, j + 1],
                        array: [...arr],
                        pass: i + 1
                    });
                }
            }
            
            // Record end of pass
            this.steps.push({
                type: 'passComplete',
                array: [...arr],
                pass: i + 1,
                sortedIndex: n - i - 1
            });
            
            if (!swapped) break;
        }
        
        return this.steps;
    }
    
    getStep(stepNumber) {
        return this.steps[stepNumber] || null;
    }
    
    getTotalSteps() {
        return this.steps.length;
    }
    
    reset() {
        this.array = [...this.originalArray];
        this.currentStep = 0;
    }
}
 
// Usage example
const visualizer = new BubbleSortVisualizer([64, 34, 25, 12, 22, 11, 90]);
const steps = visualizer.sort();
 
console.log(`Total steps: ${steps.length}`);
steps.forEach((step, index) => {
    console.log(`Step ${index + 1}: ${step.type} - [${step.array.join(', ')}]`);
});

Example 2: Bubble Sort with Animation Simulation

class AnimatedBubbleSort {
    constructor(array, delay = 500) {
        this.array = [...array];
        this.delay = delay;
        this.isRunning = false;
    }
    
    async sort() {
        if (this.isRunning) return;
        this.isRunning = true;
        
        const n = this.array.length;
        console.log('Starting animation...');
        console.log('Initial array:', this.array);
        
        for (let i = 0; i < n - 1; i++) {
            console.log(`\n--- Pass ${i + 1} ---`);
            let swapped = false;
            
            for (let j = 0; j < n - i - 1; j++) {
                // Highlight comparison
                console.log(`Comparing ${this.array[j]} and ${this.array[j + 1]}`);
                await this.sleep(this.delay);
                
                if (this.array[j] > this.array[j + 1]) {
                    // Perform swap with animation
                    console.log(`Swapping ${this.array[j]} and ${this.array[j + 1]}`);
                    [this.array[j], this.array[j + 1]] = [this.array[j + 1], this.array[j]];
                    swapped = true;
                    
                    console.log('Array after swap:', this.array);
                    await this.sleep(this.delay);
                }
            }
            
            console.log(`Pass ${i + 1} complete. Element ${this.array[n - i - 1]} is in final position.`);
            
            if (!swapped) {
                console.log('Array is sorted! Early termination.');
                break;
            }
        }
        
        console.log('\nFinal sorted array:', this.array);
        this.isRunning = false;
    }
    
    sleep(ms) {
        return new Promise(resolve => setTimeout(resolve, ms));
    }
    
    stop() {
        this.isRunning = false;
    }
}
 
// Usage
async function runAnimation() {
    const animator = new AnimatedBubbleSort([5, 2, 8, 1, 9], 1000);
    await animator.sort();
}
 
// runAnimation(); // Uncomment to run animation

Best Practices

1. Always Use the Optimized Version

// ❌ Basic version - always O(n²)
function basicBubbleSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}
 
// ✅ Optimized version - O(n) best case
function optimizedBubbleSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        let swapped = false;
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        if (!swapped) break; // Early termination
    }
    return arr;
}

2. Handle Edge Cases

function robustBubbleSort(arr) {
    // Handle edge cases
    if (!Array.isArray(arr)) {
        throw new Error('Input must be an array');
    }
    
    if (arr.length <= 1) {
        return [...arr]; // Return copy for consistency
    }
    
    // Create a copy to avoid modifying original
    const sortedArray = [...arr];
    const n = sortedArray.length;
    
    for (let i = 0; i < n - 1; i++) {
        let swapped = false;
        
        for (let j = 0; j < n - i - 1; j++) {
            // Handle potential null/undefined values
            const current = sortedArray[j];
            const next = sortedArray[j + 1];
            
            if (current != null && next != null && current > next) {
                [sortedArray[j], sortedArray[j + 1]] = [sortedArray[j + 1], sortedArray[j]];
                swapped = true;
            }
        }
        
        if (!swapped) break;
    }
    
    return sortedArray;
}

3. Use Generic Comparison Functions

function genericBubbleSort(arr, compareFunction = (a, b) => a - b) {
    const sortedArray = [...arr];
    const n = sortedArray.length;
    
    for (let i = 0; i < n - 1; i++) {
        let swapped = false;
        
        for (let j = 0; j < n - i - 1; j++) {
            if (compareFunction(sortedArray[j], sortedArray[j + 1]) > 0) {
                [sortedArray[j], sortedArray[j + 1]] = [sortedArray[j + 1], sortedArray[j]];
                swapped = true;
            }
        }
        
        if (!swapped) break;
    }
    
    return sortedArray;
}
 
// Usage examples
const numbers = [3, 1, 4, 1, 5, 9, 2, 6];
const strings = ['banana', 'apple', 'cherry', 'date'];
const objects = [
    { name: 'John', age: 30 },
    { name: 'Jane', age: 25 },
    { name: 'Bob', age: 35 }
];
 
console.log('Numbers:', genericBubbleSort(numbers));
console.log('Strings:', genericBubbleSort(strings, (a, b) => a.localeCompare(b)));
console.log('Objects by age:', genericBubbleSort(objects, (a, b) => a.age - b.age));

Conclusion

Bubble Sort is an excellent algorithm for learning fundamental sorting concepts, despite its poor performance on large datasets.

Key Takeaways

Educational Value: Perfect for understanding sorting algorithm basics
Simplicity: Easy to implement and understand
Stability: Maintains relative order of equal elements
Space Efficiency: O(1) auxiliary space requirement
Optimization Potential: Can be optimized for best-case O(n) performance

When to Choose Bubble Sort

Learning and teaching sorting algorithms
Small datasets where simplicity matters more than performance
Situations requiring stability with minimal code complexity
Memory-constrained environments where O(1) space is crucial

When to Avoid Bubble Sort

Production applications with large datasets
Performance-critical systems where efficiency matters
Any situation where JavaScript's built-in Array.sort() can be used

Final Recommendation

While Bubble Sort is not practical for most real-world applications, understanding its implementation and characteristics provides a solid foundation for learning more advanced sorting algorithms. In production JavaScript code, always prefer the built-in Array.sort() method, which is highly optimized and stable.

// Production code - use built-in sort
const numbers = [64, 34, 25, 12, 22, 11, 90];
const sorted = [...numbers].sort((a, b) => a - b);
 
// Educational code - implement bubble sort
function bubbleSort(arr) {
    const result = [...arr];
    const n = result.length;
    
    for (let i = 0; i < n - 1; i++) {
        let swapped = false;
        for (let j = 0; j < n - i - 1; j++) {
            if (result[j] > result[j + 1]) {
                [result[j], result[j + 1]] = [result[j + 1], result[j]];
                swapped = true;
            }
        }
        if (!swapped) break;
    }
    
    return result;
}

Understanding Bubble Sort helps you appreciate the elegance and efficiency of more advanced algorithms and the sophisticated optimizations in modern JavaScript engines.

Stability DSA Problems Patterns