Bubble Sort Explained: Algorithm, Code & Complexity

Bubble sort repeatedly steps through the array, compares each pair of adjacent elements, and swaps them if they are out of order. After each full pass the largest remaining element has “bubbled” to its correct place at the end. It is the slowest of the common sorts, but it is the easiest to understand — which makes it the perfect first algorithm.

The idea

Walk left to right. Whenever the left item is bigger than the right item, swap them. By the end of one pass, the biggest value sits at the far right. Repeat on the unsorted prefix; each pass locks in one more element. After at most n - 1 passes the whole array is sorted.

Tracing [5, 1, 4, 2] ascending, the first pass does: compare 5,1 → swap [1,5,4,2]; compare 5,4 → swap [1,4,5,2]; compare 5,2 → swap [1,4,2,5]. The 5 is now parked at the end.

Implementation

This version includes the standard optimization: if a full pass makes no swaps, the array is already sorted and we stop early. That is what makes a best case of O(n) possible on already-sorted input.

void bubbleSort(std::vector<int>& a) {
    int n = (int)a.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                std::swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // already sorted
    }
}

void bubbleSort(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                swapped = true;
            }
        }
        if (!swapped) break; // already sorted
    }
}

function bubbleSort(a) {
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // already sorted
  }
}

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

Complexity

• Space: O(1) — fully in-place, just a temporary for swaps.
• Stable: yes — it only swaps on strictly >, so equal elements never jump past each other.

For beginners: The inner loop bound n - 1 - i shrinks each pass because the last i elements are already in place. Forgetting that detail still sorts correctly but wastes comparisons.

When to use it

Almost never in production — its O(n²) average cost is far worse than merge sort or quick sort. Its real value is pedagogical, and the early-exit trick makes it acceptable for tiny or nearly-sorted inputs. For that niche, insertion sort is strictly better and just as simple.

Going deeper: See how all the sorts stack up on the comparison page, and in real code reach for the built-in sort.

Next: Selection Sort.