The Bubble Sort Algorithm - Bubble Sort — Understanding the Simplest Sorting Algorithm | OneNoughtOne

0/361

Data Structures & AlgorithmsBubble Sort — Intuition & Analysis

Bubble Sort — Understanding the Simplest Sorting Algorithm

LevelBeginner

Duration50 mins

TopicBubble Sort — Intuition & Analysis

1 / 4

The Bubble Sort Algorithm

The Simplest Way to Sort

Imagine you're standing in a line of people sorted by height, but the line is currently in random order. How would you organize everyone if you could only compare and swap two adjacent people at a time?

You'd naturally start at one end, compare neighbors, swap if needed, and work your way down. After one complete pass, the tallest person would be at the end. Repeat until everyone is in place.

Congratulations—you've just invented bubble sort.

Bubble sort is often the first sorting algorithm taught precisely because it mirrors this intuitive human process. It's not the most efficient algorithm, but its simplicity makes it an ideal vehicle for understanding fundamental sorting concepts that apply to every algorithm we'll study.

What You Will Learn

By the end of this page, you will understand the core intuition behind bubble sort, trace through its execution step by step, implement it in code, and visualize why it's called 'bubble' sort. This foundation prepares you for the detailed analysis in upcoming pages.

The Bubble Metaphor

The name "bubble sort" comes from a vivid physical metaphor: larger elements "bubble up" to their correct positions at the end of the array, just as air bubbles rise through water to the surface.

Consider a glass of carbonated water. Small bubbles form at the bottom and rise to the top because they're lighter than the surrounding liquid. Similarly, in bubble sort:

We repeatedly pass through the array from left to right
We compare adjacent pairs of elements
If a larger element is on the left, we swap it with its smaller neighbor
This causes larger elements to gradually migrate rightward
After each complete pass, the largest unsorted element reaches its final position

The beauty of this metaphor is that it precisely describes the algorithm's behavior: large values "float" to the right, while small values effectively "sink" to the left.

Visualizing the Bubble Effect

Picture an array as a horizontal tube of water. Each element is a bubble whose size corresponds to its value. As you pass through repeatedly, large bubbles push past smaller ones, rising toward the right end of the tube. After enough passes, all bubbles are sorted by size—largest at the right.

Why this metaphor matters for understanding:

The bubble metaphor isn't just a cute name—it reveals the algorithm's fundamental mechanism. Each pass guarantees that at least one element (the largest remaining unsorted element) reaches its final position. This is known as the loop invariant of bubble sort: after k passes, the k largest elements are in their correct, final positions at the end of the array.

Understanding this invariant is crucial because:

It explains why the algorithm terminates
It shows how progress is made with each pass
It reveals optimization opportunities (we'll explore these later)

Formal Algorithm Definition

Let's formalize the bubble sort algorithm precisely. Given an array A of n elements, bubble sort works as follows:

Bubble Sort Algorithm Steps

•Outer Loop: Repeat the following process (n-1) times, where n is the array length.
•Inner Loop: For each position i from 0 to (n - current_pass - 1), compare A[i] with A[i+1].
•Comparison: If A[i] > A[i+1] (for ascending order), the elements are out of order.
•Swap: Exchange A[i] and A[i+1] to correct the local ordering.
•Termination: After (n-1) complete passes, the array is guaranteed to be sorted.

Why (n-1) passes?

After each pass, one more element is guaranteed to be in its final position. After (n-1) passes, (n-1) elements are correctly placed. The remaining element must also be correct (there's only one spot left), so the array is sorted.

Why does the inner loop shrink?

After pass k, the k largest elements are at the end in sorted order. We don't need to compare them anymore—they're already in place. This optimization reduces unnecessary comparisons, though it doesn't change the asymptotic complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function bubbleSort(arr: number[]): number[] {
    const n = arr.length;
    
    // Outer loop: repeat (n-1) times
    for (let pass = 0; pass < n - 1; pass++) {
        // Inner loop: compare adjacent pairs
        // Note: we only go up to (n - pass - 1) because
        // the last 'pass' elements are already sorted
        for (let i = 0; i < n - pass - 1; i++) {
            // Compare adjacent elements
            if (arr[i] > arr[i + 1]) {
                // Swap if out of order
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
            }
        }
    }
    
    return arr;
}
 
// Example usage
const unsorted = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(unsorted));
// Output: [11, 12, 22, 25, 34, 64, 90]

Implementation Details Matter

Notice how we use array destructuring [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]] for swapping. This is elegant but creates a temporary array. In performance-critical code, you might use a temporary variable instead. The algorithm remains the same; only the swap mechanism differs.

Step-by-Step Execution Trace

The best way to internalize an algorithm is to trace through it manually. Let's sort a small array step by step, tracking every comparison and swap.

Initial Array: [5, 3, 8, 4, 2]

We'll perform bubble sort and observe how the largest element bubbles to the end in each pass.

Pass 1: Largest element (8) bubbles to the end
Step	Compare	Action	Array State
1.1	5 vs 3	Swap (5 > 3)	[3, 5, 8, 4, 2]
1.2	5 vs 8	No swap (5 < 8)	[3, 5, 8, 4, 2]
1.3	8 vs 4	Swap (8 > 4)	[3, 5, 4, 8, 2]
1.4	8 vs 2	Swap (8 > 2)	[3, 5, 4, 2, 8]

After Pass 1: [3, 5, 4, 2, 8] — Notice that 8 is now in its final position.

The largest element encountered the comparison gauntlet and was pushed all the way to the right. This is the "bubbling" action in its purest form.

Pass 2: Second largest (5) reaches its position
Step	Compare	Action	Array State
2.1	3 vs 5	No swap (3 < 5)	[3, 5, 4, 2, 8]
2.2	5 vs 4	Swap (5 > 4)	[3, 4, 5, 2, 8]
2.3	5 vs 2	Swap (5 > 2)	[3, 4, 2, 5, 8]

After Pass 2: [3, 4, 2, 5, 8] — Now 5 and 8 are in their final positions.

Notice we only made 3 comparisons in Pass 2 (not 4). Since 8 is already sorted, we don't need to include it.

Pass 3: Third largest (4) finds its place
Step	Compare	Action	Array State
3.1	3 vs 4	No swap (3 < 4)	[3, 4, 2, 5, 8]
3.2	4 vs 2	Swap (4 > 2)	[3, 2, 4, 5, 8]

After Pass 3: [3, 2, 4, 5, 8] — Elements 4, 5, 8 are now in final positions.

Pass 4: Final pass completes the sort
Step	Compare	Action	Array State
4.1	3 vs 2	Swap (3 > 2)	[2, 3, 4, 5, 8]

Final Result: [2, 3, 4, 5, 8] ✓

Total Statistics for this sort:

Passes: 4 (which is n-1 for n=5)
Comparisons: 4 + 3 + 2 + 1 = 10 (which is n(n-1)/2)
Swaps: 7 (depends on initial disorder)

Key Observation

Notice the pattern: each pass makes fewer comparisons than the last because more elements become "frozen" in their final positions. Pass 1 had 4 comparisons, Pass 2 had 3, Pass 3 had 2, Pass 4 had 1. The total is always n(n-1)/2 for a complete sort.

Understanding the Loop Invariant

A loop invariant is a property that remains true before and after each iteration of a loop. Understanding invariants is crucial for proving algorithm correctness and for developing algorithmic intuition.

Bubble Sort's Loop Invariant:

After the k-th pass of the outer loop, the k largest elements are in their final sorted positions at the end of the array.

Let's prove this invariant holds:

Invariant Proof Structure

•Initialization (Base Case): Before any passes (k=0), zero elements are guaranteed to be in final position. The invariant trivially holds.
•Maintenance: Assume after pass k, the k largest elements are at the end in sorted order. During pass (k+1), we compare all adjacent pairs in the unsorted portion. The largest element in this portion will be compared favorably with everyone and pushed to position (n-k-1), which is its final position. Now (k+1) largest elements are sorted at the end.
•Termination: After (n-1) passes, (n-1) largest elements are in their final positions. The smallest element must occupy the only remaining position—the first slot. The array is completely sorted.

Why invariants matter in practice:

Understanding the loop invariant helps you:

Debug with confidence — If your sort fails, check if the invariant holds after each pass
Optimize correctly — You can skip sorted regions because the invariant guarantees they're done
Extend the algorithm — Adding early termination (if no swaps occur) works because the invariant tells you when sorting is complete
Compare algorithms — Different sorting algorithms have different invariants; understanding them reveals their true nature

Inner Loop Invariant

The inner loop also has an invariant: after comparing position j with position j+1, the largest element among positions 0 through j+1 is at position j+1. This is how the largest element "bubbles" rightward during each pass.

Visualizing the Sorting Process

Visual representations help cement understanding. Let's look at bubble sort through different lenses.

As a Series of Snapshots:

Consider sorting [5, 1, 4, 2, 8]:

Initial:   [5, 1, 4, 2, 8]
           ↑  Compare & swap throughout
           
Pass 1:    [5, 1, 4, 2, 8] → [1, 5, 4, 2, 8] → [1, 4, 5, 2, 8] → [1, 4, 2, 5, 8] → [1, 4, 2, 5, 8]
                                                                                    ~~~~~~~~
                                                                                    8 is locked
           
Pass 2:    [1, 4, 2, 5, 8] → [1, 4, 2, 5, 8] → [1, 2, 4, 5, 8] → [1, 2, 4, 5, 8]
                                                                    ~~~~~~~
                                                                    5,8 locked
           
Pass 3:    [1, 2, 4, 5, 8] → [1, 2, 4, 5, 8] → [1, 2, 4, 5, 8]
                                                ~~~~~~~
                                                4,5,8 locked
           
Pass 4:    [1, 2, 4, 5, 8] → [1, 2, 4, 5, 8]
                              ~~~~~~~~~
                              All locked - Done!

As a Bar Chart (Conceptual):

Imagine each element as a bar whose height represents its value:

Initial:        After Pass 1:   After Pass 2:   Final:
    █               █               █           █
█   █   █   █   █       █   █   █       █   █   █
█   █   █   █   █   █   █   █   █   █   █   █   █
█   █   █   █   █   █   █   █   █   █   █   █   █
5   1   4   2   8   1   4   2   5 8 1   2   4 5 8 1 2 4 5 8

Watch how the tallest bar (8) moves to the right first, then 5, then 4, and so on. The right side of the array progressively becomes a sorted "staircase" of increasing bars.

The Sorted Region Grows

Think of the array as having two regions: an unsorted left portion and a sorted right portion. Initially, the entire array is unsorted. With each pass, the sorted region grows by one element as the next-largest value finds its home. This mental model applies to many sorting algorithms.

Implementation Variations

While the core algorithm remains the same, bubble sort can be implemented in various ways. Understanding these variations builds flexibility and deeper insight.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function bubbleSortOptimized(arr: number[]): number[] {
    const n = arr.length;
    
    for (let pass = 0; pass < n - 1; pass++) {
        let swapped = false; // Track if any swap occurred
        
        for (let i = 0; i < n - pass - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                swapped = true;
            }
        }
        
        // If no swaps occurred, array is already sorted
        if (!swapped) {
            break; // Early termination!
        }
    }
    
    return arr;
}
 
// For already-sorted arrays, this completes in O(n) time!
const sorted = [1, 2, 3, 4, 5];
bubbleSortOptimized(sorted); // Only one pass needed

The optimized version tracks whether any swaps occurred during a pass. If a complete pass makes no swaps, the array must already be sorted, and we can terminate early. This optimization is significant:

Already sorted arrays: O(n) time instead of O(n²)
Nearly sorted arrays: Close to O(n) time
Random arrays: Still O(n²), but might terminate a few passes early

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function bubbleSortLastSwap(arr: number[]): number[] {
    const n = arr.length;
    let lastUnsortedIndex = n - 1;
    
    while (lastUnsortedIndex > 0) {
        let lastSwapIndex = 0;
        
        for (let i = 0; i < lastUnsortedIndex; i++) {
            if (arr[i] > arr[i + 1]) {
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                lastSwapIndex = i;
            }
        }
        
        // Everything after lastSwapIndex is already sorted
        lastUnsortedIndex = lastSwapIndex;
    }
    
    return arr;
}
 
// This leverages the insight that elements after the last
// swap are already in their correct positions

This variation is even smarter: it remembers where the last swap occurred. Since no swaps happened after that point, all elements beyond it must already be sorted. The next pass only needs to go up to the last swap position.

This is particularly effective for arrays with a sorted "tail":

Array: [3, 1, 2, 4, 5, 6, 7, 8, 9, 10]
After first pass, lastSwapIndex = 1
Second pass only checks indices 0-1
Dramatically fewer comparisons than standard bubble sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function bubbleSortDescending(arr: number[]): number[] {
    const n = arr.length;
    
    for (let pass = 0; pass < n - 1; pass++) {
        for (let i = 0; i < n - pass - 1; i++) {
            // Change comparison direction: < instead of >
            if (arr[i] < arr[i + 1]) {
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
            }
        }
    }
    
    return arr;
}
 
// Example: [3, 1, 4, 1, 5] → [5, 4, 3, 1, 1]

The Core Remains the Same

All variations share the same fundamental approach: compare adjacent elements and swap if out of order. The variations optimize specific scenarios or change the sort order. Understanding the base algorithm deeply makes all variations intuitive.

Generic Bubble Sort for Any Type

Real-world sorting often involves complex objects, not just numbers. Let's build a generic bubble sort that works with any comparable type.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
type Comparator<T> = (a: T, b: T) => number;
 
function bubbleSortGeneric<T>(
    arr: T[], 
    compare: Comparator<T> = (a, b) => (a as any) - (b as any)
): T[] {
    const n = arr.length;
    
    for (let pass = 0; pass < n - 1; pass++) {
        let swapped = false;
        
        for (let i = 0; i < n - pass - 1; i++) {
            // Use the comparator: positive means a > b
            if (compare(arr[i], arr[i + 1]) > 0) {
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                swapped = true;
            }
        }
        
        if (!swapped) break;
    }
    
    return arr;
}
 
// Example 1: Sort numbers (default)
const numbers = [5, 2, 8, 1, 9];
bubbleSortGeneric(numbers);
// [1, 2, 5, 8, 9]
 
// Example 2: Sort strings by length
const words = ["elephant", "cat", "dog", "butterfly"];
bubbleSortGeneric(words, (a, b) => a.length - b.length);
// ["cat", "dog", "elephant", "butterfly"]
 
// Example 3: Sort objects by property
interface Person {
    name: string;
    age: number;
}
 
const people: Person[] = [
    { name: "Alice", age: 30 },
    { name: "Bob", age: 25 },
    { name: "Charlie", age: 35 }
];
 
bubbleSortGeneric(people, (a, b) => a.age - b.age);
// [{ name: "Bob", age: 25 }, { name: "Alice", age: 30 }, { name: "Charlie", age: 35 }]

Understanding the Comparator Pattern:

A comparator is a function that takes two elements and returns:

Negative number: first element should come before second
Zero: elements are equal (order doesn't matter)
Positive number: first element should come after second

This pattern is used universally in sorting APIs across languages:

JavaScript: Array.prototype.sort(compareFn)
Java: Comparator<T> interface
Python: key parameter or cmp_to_key
C++: std::sort with comparison function

Comparator Consistency is Critical

Your comparator must be consistent: if compare(a, b) < 0, then compare(b, a) > 0. Inconsistent comparators can cause infinite loops or incorrect results. Also ensure transitivity: if a < b and b < c, then a < c.

Common Implementation Mistakes

Even simple algorithms have pitfalls. Here are common mistakes when implementing bubble sort and how to avoid them.

Common Mistakes

•Off-by-one in outer loop: Using pass < n instead of pass < n - 1 wastes one unnecessary pass
•Off-by-one in inner loop: Using i <= n - pass - 1 causes array index out of bounds when accessing arr[i + 1]
•Forgetting the shrinking boundary: Using i < n - 1 for every pass ignores that the right side is already sorted
•Wrong swap direction: Swapping when arr[i] < arr[i+1] produces descending order
•Modifying array length during sort: Leads to unpredictable behavior

Correct Approaches

•Outer loop: for (pass = 0; pass < n - 1; pass++) — exactly n-1 passes needed
•Inner loop: for (i = 0; i < n - pass - 1; i++) — stay within bounds
•Shrinking boundary: Subtract pass from inner loop limit to skip sorted elements
•Ascending order: Swap when arr[i] > arr[i + 1]; reverse for descending
•Immutable length: Cache n = arr.length before sorting begins

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// BUG: This will crash!
function bubbleSortBuggy(arr: number[]): number[] {
    const n = arr.length;
    
    for (let pass = 0; pass < n; pass++) {  // ❌ Should be n - 1
        for (let i = 0; i <= n - 1; i++) {  // ❌ Should be < n - pass - 1
            if (arr[i] > arr[i + 1]) {      // ❌ arr[n] doesn't exist!
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
            }
        }
    }
    return arr;
}
 
// When i = n - 1, we access arr[n] which is undefined
// Comparing arr[n-1] > undefined returns false, avoiding obvious crash
// But arr[n-1] might incorrectly not be swapped with its actual neighbor

Testing Edge Cases

Always test your implementation with: empty array [], single element [5], two elements [5, 3] and [3, 5], already sorted array, reverse sorted array, array with duplicates, and large arrays. These edge cases catch most bugs.

Summary: The Bubble Sort Algorithm

We've covered bubble sort thoroughly. Let's consolidate the key takeaways:

Key Takeaways

•The bubble metaphor is literal: Larger elements "bubble up" to the right end of the array, just as air bubbles rise through water.
•Simple algorithm, simple implementation: Compare adjacent pairs, swap if out of order, repeat until sorted. Two nested loops, one comparison, one swap.
•The loop invariant guarantees correctness: After k passes, the k largest elements are in their final positions. This is why (n-1) passes guarantee a sorted array.
•Optimizations exist: Early termination when no swaps occur, tracking last swap position—these help in best-case scenarios but don't change worst-case complexity.
•Generic implementations are straightforward: Use a comparator function to sort any type of data, not just numbers.
•Watch for off-by-one errors: The inner loop especially is prone to boundary mistakes. Test edge cases rigorously.

What's next:

Now that you understand the bubble sort algorithm conceptually and can implement it, we'll dive deeper into how it works mechanically. The next page explores the swapping mechanism—the fundamental operation that makes bubble sort (and many other algorithms) possible.

Page Complete

You now understand the bubble sort algorithm: its metaphor, mechanism, invariants, and implementation. You've traced through examples, seen variations, and learned to avoid common mistakes. Next, we'll examine the adjacent swap operation in detail.