Bubble Sort

A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.

Algorithm Information

Time Complexity

Best: O(n)
Average: O(n²)
Worst: O(n²)

Space Complexity

O(1)

Properties

• Stable sorting algorithm
• In-place sorting
• Comparison-based
1/50
Speed: 1x

Algorithm Code

1function bubbleSort(arr) {
2  const n = arr.length;
3  
4  for (let i = 0; i < n - 1; i++) {
5    let swapped = false;
6    
7    for (let j = 0; j < n - i - 1; j++) {
8      // Compare adjacent elements
9      if (arr[j] > arr[j + 1]) {
10        // Swap elements
11        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
12        swapped = true;
13      }
14    }
15    
16    // If no swapping occurred, array is sorted
17    if (!swapped) break;
18  }
19  
20  return arr;
21}

Variable State

i:0
j:0
n:7
swapped:false

Array Visualization

Watch how bubble sort compares and swaps adjacent elements

640
341
252
123
224
115
906

Statistics

Comparisons0
Swaps0
Step1 / 50

Legend

Comparing
Swapping
Sorted
Unsorted

Starting bubble sort algorithm

How Bubble Sort Works

Learn the fundamentals of bubble sort through step-by-step explanations, code examples, and key concepts.

Algorithm Overview

Bubble Sort is one of the simplest sorting algorithms to understand. It works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they're in the wrong order. The pass through the list is repeated until the list is sorted.

Why is it called "Bubble Sort"?

The algorithm gets its name because smaller elements "bubble" to the top (beginning) of the list, just like air bubbles rise to the surface of water. In each pass, the largest unsorted element "bubbles" to its correct position at the end.

Step-by-Step Process

1

Compare Adjacent Elements

Start at the beginning of the array and compare the first two elements. If the first element is greater than the second, swap them.

if (arr[0] > arr[1]) {
  swap(arr[0], arr[1]);
}
2

Move to Next Pair

Continue comparing adjacent pairs throughout the entire array. Each comparison may result in a swap if elements are out of order.

for (let i = 0; i < n-1; i++) {
  if (arr[i] > arr[i+1]) {
    swap(arr[i], arr[i+1]);
  }
}
3

Complete the Pass

After one complete pass, the largest element will have "bubbled up" to the end. This element is now in its correct final position.

Key Insight: After each pass, one more element is guaranteed to be in its correct position!
4

Repeat Until Sorted

Repeat the process for the remaining unsorted portion. Each pass reduces the problem size by one element.

for (let pass = 0; pass < n-1; pass++) {
  // Each pass bubbles one element to correct position
  for (let i = 0; i < n-1-pass; i++) {
    if (arr[i] > arr[i+1]) swap(arr[i], arr[i+1]);
  }
}

Complete Implementation

Here's the complete bubble sort implementation with detailed comments:

function bubbleSort(arr) {
    const n = arr.length;
    
    // Outer loop: number of passes needed
    for (let i = 0; i < n - 1; i++) {
        let swapped = false; // Optimization flag
        
        // Inner loop: compare adjacent elements
        // Note: n-1-i because last i elements are already sorted
        for (let j = 0; j < n - 1 - i; j++) {
            
            // Compare adjacent elements
            if (arr[j] > arr[j + 1]) {
                // Swap if they're in wrong order
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        
        // If no swapping occurred, array is already sorted
        if (!swapped) {
            break; // Early termination optimization
        }
    }
    
    return arr;
}

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

Key Concepts & Optimizations

✅ Advantages

  • •Simple to understand: Very intuitive algorithm concept
  • •Stable: Equal elements maintain their relative order
  • •In-place: Only requires O(1) extra memory
  • •Adaptive: Performs better on nearly sorted data

❌ Disadvantages

  • •Slow performance: O(n²) time complexity
  • •Many comparisons: Always compares adjacent elements
  • •Not practical: Too slow for large datasets
  • •Many swaps: Elements move slowly to final positions

💡 Optimization: Early Termination

The swapped flag allows the algorithm to detect when the array becomes sorted before all passes are complete. If no swaps occur during a pass, the array is already sorted and we can terminate early. This improves best-case performance from O(n²) to O(n).

Complexity Analysis

Best Case

O(n)

When array is already sorted. Only one pass needed with early termination.

Average Case

O(n²)

Random order data requires approximately n²/2 comparisons and swaps.

Worst Case

O(n²)

Reverse sorted array. Requires maximum number of comparisons and swaps.

Mathematical Analysis

Pass 1: (n-1) comparisons
Pass 2: (n-2) comparisons
Pass 3: (n-3) comparisons
...
Pass (n-1): 1 comparison
Total: (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)

When to Use Bubble Sort

✅ Good for:

  • • Learning: Understanding sorting algorithm concepts
  • • Small datasets: Arrays with fewer than 10-20 elements
  • • Nearly sorted data: Takes advantage of early termination
  • • Educational purposes: Demonstrating algorithm behavior
  • • Simple implementation: When code simplicity is priority

❌ Avoid for:

  • • Large datasets: Performance becomes unacceptable
  • • Production systems: Much better alternatives available
  • • Time-critical applications: O(n²) is too slow
  • • Random data: No performance benefits
  • • Memory-constrained systems: Too many swaps

🎓 Educational Value

While bubble sort isn't practical for real-world applications, it's invaluable for learning. It introduces key concepts like comparisons, swaps, loop invariants, and optimization techniques that apply to more advanced algorithms. Understanding bubble sort provides a foundation for learning more efficient sorting methods.