Bubble Sort Explained with Visualizations

Bubble sort is often the first sorting algorithm you learn in a computer science course. It's not the fastest, but it's one of the most intuitive — and understanding it builds the foundation for understanding more advanced algorithms.

How Bubble Sort Works

The idea is beautifully simple: walk through the list, compare each pair of adjacent elements, and swap them if they're in the wrong order. Repeat until no more swaps are needed.

It's called "bubble" sort because larger elements "bubble up" to the end of the list with each pass, like bubbles rising in water.

Step by Step

Let's sort [5, 3, 8, 1, 2]:

Pass 1:

• Compare 5 and 3: swap → [3, 5, 8, 1, 2]
• Compare 5 and 8: no swap → [3, 5, 8, 1, 2]
• Compare 8 and 1: swap → [3, 5, 1, 8, 2]
• Compare 8 and 2: swap → [3, 5, 1, 2, 8]

After pass 1, the largest element (8) is in its final position.

Pass 2:

• Compare 3 and 5: no swap → [3, 5, 1, 2, 8]
• Compare 5 and 1: swap → [3, 1, 5, 2, 8]
• Compare 5 and 2: swap → [3, 1, 2, 5, 8]

Now 5 is in its final position.

Pass 3:

• Compare 3 and 1: swap → [1, 3, 2, 5, 8]
• Compare 3 and 2: swap → [1, 2, 3, 5, 8]

Pass 4:

• Compare 1 and 2: no swap → [1, 2, 3, 5, 8]

Sorted! No swaps in this pass, so we know we're done.

The Code

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break  # Already sorted!
    return arr

The swapped flag is an optimization: if no swaps happen in a complete pass, the list is already sorted and we can stop early.

The Optimization: Early Termination

The swapped flag deserves more attention because it transforms bubble sort's behavior on nearly-sorted data. Without it, bubble sort always runs all n-1 passes regardless of whether the array became sorted partway through. With the flag, we track whether any swap occurred during a pass. If a full pass completes with zero swaps, every adjacent pair is already in order, which means the entire array is sorted.

Consider a concrete example. Suppose you have [1, 2, 4, 3, 5, 6, 7, 8] --- an eight-element array where only 4 and 3 are out of place. Without early termination, bubble sort would still perform seven passes. But with the swapped flag, here's what happens:

Pass 1: We compare each adjacent pair. The only swap is 4 and 3: [1, 2, 3, 4, 5, 6, 7, 8]. We set swapped = True.

Pass 2: We walk through the entire array. 1 ≤ 2, 2 ≤ 3, 3 ≤ 4, 4 ≤ 5, 5 ≤ 6, 6 ≤ 7, 7 ≤ 8. Zero swaps. swapped stays False, so we break out of the loop.

That's just 2 passes instead of 7 --- a huge saving. In the best case, when the input is already perfectly sorted, bubble sort with early termination finishes in a single pass with n-1 comparisons and zero swaps, giving it O(n) performance.

This adaptive behavior is especially useful in scenarios where data arrives mostly sorted. For example, if you maintain a sorted list and a new element is appended at the end, a single bubble sort pass from right to left can place it correctly. Similarly, if a few elements shift slightly out of position due to incremental updates, bubble sort with early termination handles the correction efficiently. The optimization is trivially easy to implement --- just a boolean variable and one if statement --- yet it fundamentally changes the algorithm's behavior on favorable inputs.

Time Complexity

Space complexity: O(1) — bubble sort sorts in-place, using only a constant amount of extra memory.

Why O(n²)?

In the worst case, we need n-1 passes, and each pass compares up to n-1 pairs. That's roughly n × n = n² comparisons.

For 10 elements, that's ~100 operations. Fine. For 1,000 elements, that's ~1,000,000 operations. Still okay. For 1,000,000 elements, that's ~1,000,000,000,000 operations. That could take hours.

This is why bubble sort is impractical for large datasets.

Properties of Bubble Sort

Stable: Equal elements maintain their relative order. If two students have the same grade, they'll stay in their original order after sorting.

In-place: Uses O(1) extra memory. No need to create a copy of the array.

Adaptive: With the early termination optimization, it runs in O(n) on already-sorted or nearly-sorted data.

Simple: Easy to understand, implement, and debug. The entire algorithm is about 10 lines of code.

When to Use Bubble Sort

Use it when:

• You're learning about sorting algorithms (that's why it's taught first!)
• The dataset is very small (< 50 elements)
• The data is nearly sorted (the early termination makes it efficient)
• You need a stable sort with minimal code

Don't use it when:

• Performance matters (use quick sort or merge sort instead)
• The dataset is large
• The data is randomly ordered or reverse sorted

Bubble Sort vs Other Algorithms

Insertion sort is often a better choice than bubble sort for small or nearly-sorted data — it's also O(n²) in the worst case but typically does fewer swaps.

Common Variations

Cocktail Shaker Sort: Instead of always going left-to-right, alternate between left-to-right and right-to-left passes. This helps elements that need to move in both directions.

Comb Sort: Instead of comparing adjacent elements, compare elements with a gap that shrinks over time. This addresses bubble sort's main weakness — small values at the end of the list ("turtles") that move very slowly.

Practice These Concepts

Apply sorting concepts to real coding problems:

• 3Sum — Sort first, then use two pointers for O(n²)
• Kth Largest Element — Compare sorting vs quickselect vs heap approaches

Related Articles

• What is an Algorithm? The Complete Beginner's Guide — Start here if you're new to algorithms
• Big O Notation: A Practical Guide — Understand why bubble sort is O(n²)
• Quick Sort: How It Works Step by Step — See a much faster O(n log n) alternative
• Insertion Sort: Simple, Stable, and Underrated — A better O(n²) algorithm for small data

See It In Action

Reading about bubble sort is one thing. Watching it happen is another.

Our interactive visualization lets you step through bubble sort one comparison at a time. You'll see elements light up as they're compared, watch swaps happen in real-time, and see the sorted portion grow with each pass. You can adjust the speed, change the array size, and compare it side-by-side with other sorting algorithms.

There's no faster way to build intuition for how sorting works.