Free lesson · DSA Mastery - Interview Prep, End to End

Bubble Sort

Easy11 min readdsasorting-algorithms

Bubble Sort

Bubble Sort is the algorithm most people learn first, and for good reason - it is genuinely the simplest comparison-based sort to understand. You walk through the array, comparing each pair of adjacent elements, and you swap them if they are out of order. Do that enough times and the array is sorted.

It is also one of the slowest algorithms you will encounter for any non-trivial input. So why do we teach it first? Because the mechanics are transparent, the invariants are easy to see, and once you understand Bubble Sort, the more sophisticated sorts make sense as solutions to specific problems Bubble Sort has.

In this chapter, we will walk through how Bubble Sort works, trace it on a real example, look at why it is slow, and figure out the (narrow) situations where it is actually useful.

What Is Bubble Sort?

Imagine you are organizing a row of cards by walking down the line, looking at each pair of adjacent cards, and swapping them if the left one is bigger than the right one. After one full pass, the biggest card has "bubbled" all the way to the right end - it ended up there because every comparison it was involved in pushed it one step further right.

That is the algorithm. The name comes from how the largest elements "bubble" to the end of the array, one position per pass.

The strategy in plain steps:

1. Start at the beginning of the array.
2. Compare the first pair (positions 0 and 1). If they are out of order, swap them.
3. Move one step right. Compare positions 1 and 2. Swap if out of order.
4. Keep going until you reach the end. After this pass, the largest element is at the last position.
5. Start over from the beginning. This time, you only need to go to the second-to-last position because the last one is already correct.
6. Repeat. Each pass shrinks the unsorted region by one.

graph TD
    A["Unsorted Array<br/>[5, 2, 8, 1, 9, 3]"] --> B["Compare Adjacent Pairs"]
    B --> C{"Pair out<br/>of order?"}
    C -->|Yes| D["Swap them"]
    C -->|No| E["Move on"]
    D --> F["Move one position right"]
    E --> F
    F --> G{"End of unsorted<br/>region?"}
    G -->|No| B
    G -->|Yes| H{"Any swaps<br/>this pass?"}
    H -->|Yes| B
    H -->|No| I["Sorted: [1, 2, 3, 5, 8, 9]"]
    
    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9

This diagram shows the Bubble Sort algorithm as a loop. The algorithm compares adjacent pairs in the array, swapping any pair that is out of order. After moving through the unsorted region, the algorithm checks whether any swaps happened this pass. If yes, it goes again. If no, the array is sorted. The largest element bubbles to the end of the unsorted region with each pass.

After pass i, the last i + 1 elements are guaranteed sorted. They hold the i + 1 largest values in order. This is the opposite of Selection Sort, which grows its sorted region from the left.

How It Works

Let us look at the pieces.

The Adjacent Comparison

The atomic operation of Bubble Sort is comparing two neighboring elements at positions j and j + 1. If arr[j] > arr[j + 1], they are out of order - the smaller one should be on the left. We swap them.

In Java, the swap is the same three-line dance you see everywhere:

int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;

If arr[j] <= arr[j + 1], we leave them alone and move on.

The Pass

A "pass" walks from the start of the array to the end of the unsorted region, doing the adjacent comparison at each step. The key insight is that one pass always places the largest unsorted element at the end of the unsorted region.

Here is why. Imagine the largest element starts at some position k. The first comparison at k - 1 vs k finds it bigger than its left neighbor - no swap. The comparison at k vs k + 1 finds it bigger than its right neighbor - swap. Now the largest is at position k + 1. The comparison at k + 1 vs k + 2 finds it bigger - swap. And so on, all the way to the end.

In one pass, the largest element travels from wherever it was to the end. Every other element might shuffle by one position at most.

The Early Exit Optimization

Here is where Bubble Sort gets interesting. If a pass completes without making any swaps, you know the array is sorted - there is no remaining work. You can exit early.

This is what makes Bubble Sort's best case O(n) instead of O(n²). Feed it an already-sorted array and it does exactly one pass, makes zero swaps, and quits.

The optimization requires a swapped flag:

boolean swapped = false;
// ... do the pass, set swapped = true on any swap ...
if (!swapped) break;

It is a small change that fundamentally changes the algorithm's behavior on nice inputs. Without it, Bubble Sort would always be O(n²) regardless of how sorted the input was.

The Full Algorithm

Putting the pieces together:

1. For each pass i from 0 to n - 2:
   • Set swapped = false.
   • For each position j from 0 to n - i - 2:
     • If arr[j] > arr[j + 1], swap and set swapped = true.
   • If no swaps happened (swapped == false), exit early.
2. When the loop finishes (or exits early), the array is sorted.

The n - i - 2 upper bound in the inner loop is the optimization: after pass i, the last i + 1 elements are sorted, so we do not need to look at them again.

Code Implementation

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        
        if (!swapped) break;
    }
}

// Usage:
// int[] arr = {5, 2, 8, 1, 9, 3};
// bubbleSort(arr);
// System.out.println(Arrays.toString(arr));
// Output: [1, 2, 3, 5, 8, 9]

This Java code implements Bubble Sort with the early-exit optimization. The outer loop runs for each pass from zero to n minus two. Inside each pass, a swapped flag tracks whether any swaps occurred. The inner loop scans from position zero to n minus i minus two, comparing adjacent pairs and swapping if out of order. After each pass, if no swaps occurred the algorithm exits early because the array is sorted. The bubbleSort function modifies the array in place.

Two things worth pointing out:

The outer loop bound is n - 1 because we never need a final pass when only one element is "unsorted" - a single element is trivially in place. The inner loop bound n - i - 1 skips the elements that previous passes already placed.

The swapped flag is small but does real work. Without it, this would be O(n²) on every input. With it, the best case drops to O(n).

Example Walkthrough

Let us trace Bubble Sort on [5, 2, 8, 1, 9, 3]. Six elements, so we will do up to five passes.

Pass 1 (i = 0)

Walk from position 0 to position 4. We are looking for adjacent pairs that are out of order.

Initial: [5, 2, 8, 1, 9, 3]

j=0: compare arr[0]=5, arr[1]=2.  5 > 2, swap.
     [2, 5, 8, 1, 9, 3]
j=1: compare arr[1]=5, arr[2]=8.  5 < 8, no swap.
j=2: compare arr[2]=8, arr[3]=1.  8 > 1, swap.
     [2, 5, 1, 8, 9, 3]
j=3: compare arr[3]=8, arr[4]=9.  8 < 9, no swap.
j=4: compare arr[4]=9, arr[5]=3.  9 > 3, swap.
     [2, 5, 1, 8, 3, 9]

End of pass 1. swapped = true.
9 is now at the end. The last position is locked in.

Three swaps in pass 1. The 9 bubbled all the way from position 4 to position 5. Notice the largest element ends up in its final position after just one pass - this is the guarantee Bubble Sort gives.

Pass 2 (i = 1)

Now we only scan positions 0 to 3 (the inner bound is n - i - 1 = 6 - 1 - 1 = 4, so j goes 0, 1, 2, 3).

Start: [2, 5, 1, 8, 3, 9]

j=0: compare arr[0]=2, arr[1]=5.  2 < 5, no swap.
j=1: compare arr[1]=5, arr[2]=1.  5 > 1, swap.
     [2, 1, 5, 8, 3, 9]
j=2: compare arr[2]=5, arr[3]=8.  5 < 8, no swap.
j=3: compare arr[3]=8, arr[4]=3.  8 > 3, swap.
     [2, 1, 5, 3, 8, 9]

End of pass 2. swapped = true.
8 is now in its final position.

Two swaps in pass 2. The 8 traveled to position 4. Both the largest and second-largest are now locked in at the end.

Pass 3 (i = 2)

Inner loop runs j = 0 to 2.

Start: [2, 1, 5, 3, 8, 9]

j=0: compare arr[0]=2, arr[1]=1.  2 > 1, swap.
     [1, 2, 5, 3, 8, 9]
j=1: compare arr[1]=2, arr[2]=5.  2 < 5, no swap.
j=2: compare arr[2]=5, arr[3]=3.  5 > 3, swap.
     [1, 2, 3, 5, 8, 9]

End of pass 3. swapped = true.

The array is now actually sorted, but Bubble Sort does not know it yet. It will do one more pass to confirm.

Pass 4 (i = 3)

Inner loop runs j = 0 to 1.

Start: [1, 2, 3, 5, 8, 9]

j=0: compare arr[0]=1, arr[1]=2.  1 < 2, no swap.
j=1: compare arr[1]=2, arr[2]=3.  2 < 3, no swap.

End of pass 4. swapped = false.
Early exit!

Pass 4 makes no swaps, so the swapped flag stays false, and the algorithm exits. The array is sorted.

Final sorted array: [1, 2, 3, 5, 8, 9]

The total swap count was 6 - three in pass 1, two in pass 2, one in pass 3, zero in pass 4. For comparison, Selection Sort needed only 3 swaps on the same input. Bubble Sort uses more swaps because every adjacent out-of-order pair triggers a swap, while Selection Sort waits until it has found the minimum and does just one swap per pass.

graph TD
    A["Pass 0 (initial)<br/>[5, 2, 8, 1, 9, 3]"] --> B["Pass 1<br/>[2, 5, 1, 8, 3, 9]<br/>9 in place"]
    B --> C["Pass 2<br/>[2, 1, 5, 3, 8, 9]<br/>8 in place"]
    C --> D["Pass 3<br/>[1, 2, 3, 5, 8, 9]<br/>everything in place"]
    D --> E["Pass 4 (verify)<br/>[1, 2, 3, 5, 8, 9]<br/>no swaps, exit"]
    
    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9

This diagram shows the array state after each pass of Bubble Sort. Pass zero is the initial unsorted array. After pass one, nine is in its final position. After pass two, eight is in place. After pass three, all elements are in place. Pass four does a verification pass with no swaps and exits early thanks to the swapped flag optimization. The sorted region grows from the right edge.

The sorted region grows from the right in Bubble Sort. That is the opposite of Selection Sort, which grows from the left.

Complexity Analysis

Stability: Bubble Sort is stable. The swap condition is strict (>), not >=, so equal elements never get swapped past each other. Their relative order is preserved.

Why the Best Case Is O(n)

This is where the early exit pays off. If the array is already sorted, the first pass makes zero swaps. The swapped flag stays false, the algorithm exits, and the total work is just one pass - n - 1 comparisons. That is O(n).

Without the early exit, Bubble Sort would do n - 1 passes regardless, each one slightly shorter than the last, for a total of O(n²) work even on sorted input. The optimization is genuinely meaningful.

Why the Worst Case Is O(n²)

For a reverse-sorted input like [6, 5, 4, 3, 2, 1], every adjacent pair is out of order. Every pass has to bubble the largest remaining element from the start to its position, and that requires comparing and swapping every pair along the way.

Total comparisons: (n-1) + (n-2) + ... + 1 = n(n-1)/2, which is O(n²). And every comparison results in a swap, so total swap count is also O(n²).

Why It Is Stable

Stability matters when sorting records by one key. Equal records should keep their original relative order. Bubble Sort guarantees this because we only swap when arr[j] > arr[j + 1] - strictly greater. Equal elements never get swapped, so their original order is preserved.

This is a real advantage over Selection Sort (which is not stable in its standard form). For sorting structured records, Bubble Sort's stability is sometimes the deciding factor.

When to Use Bubble Sort

Good Fit

• Teaching introductory algorithms. Bubble Sort's mechanics are transparent enough that anyone can follow them. It is a fantastic first sort to learn.
• Tiny arrays where simplicity matters. For n < 10 elements, all O(n²) sorts are essentially indistinguishable from O(n log n) sorts. Bubble Sort wins on code size if you need a one-off sort inside a function and do not want to invoke Arrays.sort().
• Nearly-sorted data, in tight loops. Bubble Sort's early-exit best case means it can be fast on data that is almost-sorted. If you know your input has only a few elements out of place, Bubble Sort might be acceptable.
• Embedded systems or extreme memory constraints. The implementation is tiny - a handful of lines, no extra data structures, no recursion. For environments where every byte of code matters, Bubble Sort is a defensible choice.

Not Ideal For

• General-purpose sorting. For anything beyond toy sizes, use Arrays.sort() (which uses dual-pivot quicksort) or Collections.sort() (which uses TimSort).
• Large datasets. A 100,000-element Bubble Sort is 5 billion operations - minutes of compute for what should be milliseconds.
• Production code at any scale. There is essentially no scenario where Bubble Sort is the right choice in production code. The simplicity advantage matters in lecture halls, not in shipped systems.

Bubble Sort vs Selection Sort

These two are often introduced together. The trade-offs are worth knowing:

Each beats the other on different dimensions. Bubble Sort wins on best case and stability. Selection Sort wins on swap count and predictability. Neither is the right answer at production scale - but understanding their trade-offs is how you start reasoning about sorting in general.

In the next chapters, we move to Insertion Sort (another O(n²) algorithm but the most practical of the three) and then to the O(n log n) sorts that handle real workloads. Bubble Sort is the foundation. Everything else is a reaction to Bubble Sort's limitations.

Back to DSA Mastery - Interview Prep, End to End