Free explainer · Video · Code · Quiz

Bubble Sort

Sweep the array, swapping neighbours that are out of order, so the biggest value bubbles to the end each pass. A stable, in-place bubble sort that stops as soon as a sweep makes no swap: O(n) when sorted, O(n²) otherwise.

Difficulty: Easy
Time: O(n²) worst, O(n) best
Space: O(1)

Take the quiz

How it works

The idea, a worked example, and the traps to avoid.

The idea

Picture a row of people lining up by height. You walk along the row, and whenever the person on your left is taller than the person on your right, you ask them to trade places. When you reach the end, the tallest person has been carried all the way to the right, like a bubble rising to the surface. Walk the row again and the second tallest settles next to them. Keep walking until a whole trip needs no swaps at all: the row is in order.

That's bubble sort. It only ever looks at two neighbours and fixes them if they're in the wrong order. It's slow, but it's the easiest sorting algorithm to read, which is why it's usually the first one you meet.

Two details make this version tidy:

Each pass is one shorter. After pass 1 the biggest value is in its final place, after pass 2 the two biggest are, and so on. So the inner loop stops earlier every time (j + 1 < n - i).
Early exit. A flag, swapped, records whether the pass moved anything. If it didn't, every neighbouring pair is already in order, so the whole array is, and we stop.

Walkthrough

Sort [5, 2, 8, 1, 7, 3, 6, 4]. Each pass compares neighbours left to right and swaps when the left one is strictly bigger.

Pass	Compares	Swaps	Array after the pass
1	7	6	`[2, 5, 1, 7, 3, 6, 4 │ 8]`
2	6	4	`[2, 1, 5, 3, 6, 4 │ 7, 8]`
3	5	3	`[1, 2, 3, 5, 4 │ 6, 7, 8]`
4	4	1	`[1, 2, 3, 4 │ 5, 6, 7, 8]`
5	3	0	`[1, 2, 3, 4 │ 5, 6, 7, 8]`

The bar marks the part that is already final. In pass 1 the 8 is picked up at index 2 and carried to the end: it swaps with 1, 7, 3, 6 and 4 in turn. Pass 5 finds nothing to swap, swapped stays false, and the sort stops. That's 25 comparisons and 14 swaps in total.

The swap count is no accident: every swap fixes exactly one inversion (a pair that is out of order), and this array has 14 of them. Bubble sort does as many swaps as there are inversions, no more and no fewer.

Why it's correct

After pass i, the i biggest values sit at the end of the array in their final order. Pass 1 proves it for one value: carrying the running maximum rightwards, a bigger value always wins the swap, so the overall maximum is never left behind and ends at the last index. Every later pass repeats this on the shorter prefix that is left.

If a pass makes no swap, then values[j] <= values[j + 1] for every neighbouring pair in the prefix, which is exactly what "sorted" means. Stopping there is safe, and running to the end of the outer loop is also safe: after n - 1 passes only one value is left, and it has nowhere else to go.

Complexity

Worst and average: O(n²). Pass i makes n - 1 - i comparisons, which adds up to n(n - 1) / 2. A reversed array also needs that many swaps. A random one needs about half as many, but it's still quadratic.
Best: O(n). On an already sorted array the first pass finds nothing to swap and the early exit stops after n - 1 comparisons. Without the swapped flag, bubble sort is always quadratic.
Space: O(1). It swaps in place with one temporary variable.
Stable. The comparison is strict (>), so two equal values are never swapped and keep their original order. Sort people by city and then by age, and people of the same age stay in city order. Switch to >= and you lose stability, and make extra swaps for nothing.

Common bugs

Forgetting that the inner loop shrinks. Letting j run to the end of the array on every pass still sorts correctly, but it re-compares the values that are already final.
Off by one at the end of the row. The inner loop reads values[j + 1], so j must stop at n - i - 2. In the listing, j + 1 < n - i takes care of it.
Resetting swapped in the wrong place. It must be reset at the start of each pass. Set it once outside the outer loop and a single swap in pass 1 keeps the early exit from ever firing.
Using >= instead of >. It still sorts, but it swaps equal values for nothing and breaks stability.
Unsigned counters in C++. With std::size_t, n - 1 wraps around for an empty array. The listing writes the bounds as i + 1 < n for that reason.

When to use it (and when not)

Use it to learn sorting, to teach loop invariants, or for arrays that are tiny or almost sorted, where the early exit makes it a single cheap pass. It's also handy when you want the simplest possible stable in-place sort and speed doesn't matter.

For real workloads, don't. On a thousand elements, a quadratic sort already does around half a million comparisons, against roughly ten thousand for merge sort or quick sort. Insertion sort is usually the better simple sort: same O(n²) and O(n) best case, but far fewer writes. In real projects, call the language's built-in sort.

Interview variations

Cocktail shaker sort. Sweep right, then left, then right again. Small values near the end travel left quickly, which plain bubble sort does at one step per pass.
Count the swaps. The minimum number of adjacent swaps to sort an array equals its number of inversions. Count them in O(n log n) with a merge sort instead of simulating.
Sort with at most k passes, or find the k-th largest. After k passes, the k biggest values are in place. That solves "k largest" in O(nk), fine for tiny k.
Is this array sorted after one pass? One pass sorts an array exactly when no value has to move left by more than one place. A classic question about what a single bubble pass can do.

Code

The same algorithm, step for step, in 4 languages.

JavaScript

// Bubble sort with an early exit: sweep the array, swapping neighbours that are out of order.
// Each sweep carries the biggest remaining value to the end; a sweep with no swap means done.

/**
 * Sorts `values` in ascending order, in place.
 * Stable: only a strictly bigger value moves past its neighbour, so equals keep their order.
 *
 * @param {number[]} values the array to sort
 * @returns {void}
 */
export function bubbleSort(values) {
  const n = values.length;

  for (let i = 0; i + 1 < n; i++) {
    let swapped = false;

    for (let j = 0; j + 1 < n - i; j++) {
      if (values[j] > values[j + 1]) {
        const tmp = values[j];
        values[j] = values[j + 1];
        values[j + 1] = tmp;
        swapped = true;
      }
    }

    if (!swapped) {
      break; // a whole sweep without a swap: already sorted
    }
  }
}

# Bubble sort with an early exit: sweep the array, swapping neighbours that are out of order.
# Each sweep carries the biggest remaining value to the end; a sweep with no swap means done.
from typing import List


def bubble_sort(values: List[int]) -> None:
    """Sort values in ascending order, in place.

    Stable: only a strictly bigger value moves past its neighbour, so equals keep their order.
    """
    n = len(values)

    for i in range(n - 1):
        swapped = False

        for j in range(n - 1 - i):
            if values[j] > values[j + 1]:
                tmp = values[j]
                values[j] = values[j + 1]
                values[j + 1] = tmp
                swapped = True

        if not swapped:
            break  # a whole sweep without a swap: already sorted

/**
 * Bubble sort with an early exit: sweep the array, swapping neighbours that are out of order.
 * Each sweep carries the biggest remaining value to the end; a sweep with no swap means done.
 */
public final class BubbleSort {
    private BubbleSort() {
    }

    /**
     * Sorts values in ascending order, in place.
     * Stable: only a strictly bigger value moves past its neighbour, so equals keep their order.
     */
    public static void bubbleSort(int[] values) {
        int n = values.length;

        for (int i = 0; i + 1 < n; i++) {
            boolean swapped = false;

            for (int j = 0; j + 1 < n - i; j++) {
                if (values[j] > values[j + 1]) {
                    int tmp = values[j];
                    values[j] = values[j + 1];
                    values[j + 1] = tmp;
                    swapped = true;
                }
            }

            if (!swapped) {
                break; // a whole sweep without a swap: already sorted
            }
        }
    }
}

// Bubble sort with an early exit: sweep the array, swapping neighbours that are out of order.
// Each sweep carries the biggest remaining value to the end; a sweep with no swap means done.
#include <cstddef>
#include <vector>

// Sorts values in ascending order, in place.
// Stable: only a strictly bigger value moves past its neighbour, so equals keep their order.
void bubbleSort(std::vector<int>& values) {
    std::size_t n = values.size();

    for (std::size_t i = 0; i + 1 < n; i++) {
        bool swapped = false;

        for (std::size_t j = 0; j + 1 < n - i; j++) {
            if (values[j] > values[j + 1]) {
                int tmp = values[j];
                values[j] = values[j + 1];
                values[j + 1] = tmp;
                swapped = true;
            }
        }

        if (!swapped) {
            break;  // a whole sweep without a swap: already sorted
        }
    }
}

Ask about this algorithm

Stuck on a step? Ask for another example or why it works.

Test yourself

10 quick questions to check it stuck.

Q1 · Bubble sort runs one pass over [5, 2, 8, 1, 7, 3, 6, 4]. What does the array look like after it?

Take the quiz