Bubble Sort

The idea

Bubble sort repeatedly walks through the array and compares neighbouring elements. If a pair is in the wrong order, it swaps them.

After one full pass, the largest value has been pushed all the way to the end — like a bubble rising to the top of water. After the second pass, the second-largest is in place, and so on.

Analogy: lining up students by height by only letting neighbours swap places. The tallest student keeps swapping forward until they reach the end of the line.

Step by step

For an array of n elements:

1. Pass 1: compare positions (0,1), (1,2), …, (n−2, n−1). Swap any pair where the left is bigger. Now the biggest element is at index n−1.
2. Pass 2: do the same but stop one earlier — the last element is already final.
3. Keep going. After n−1 passes, everything is sorted.

Optimisation: keep a flag swapped. If a whole pass makes no swaps, the array is already sorted — stop early. This makes the best case (already sorted input) only O(n).

In the model, green bars are in their final position; the yellow pair is being compared; red means a swap. Swapped bars arc around each other in 3D so you can follow them.

Code

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):          # the last i items are already in place
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:                      # no swaps → already sorted
            break
    return a

print(bubble_sort([5, 1, 4, 2, 8]))   # [1, 2, 4, 5, 8]

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

void bubbleSort(vector<int>& a) {
    int n = 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]) {
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

int main() {
    vector<int> a = {5, 1, 4, 2, 8};
    bubbleSort(a);
    for (int x : a) cout << x << " ";   // 1 2 4 5 8
}

How slow is it?

Pass 1 makes n−1 comparisons, pass 2 makes n−2, … down to 1:

(n−1) + (n−2) + … + 1 = n(n−1)/2

For 10 elements that’s 45 comparisons; for 10,000 elements, almost 50 million. Because the work grows with n², bubble sort is called a quadratic, O(n²) algorithm. Compare that with merge sort, which needs only about 130,000 comparisons for 10,000 elements.

Properties

When would you actually use it?

Honestly, almost never in real software — but it is the perfect first sorting algorithm because it teaches comparisons, swaps, passes, loop invariants and Big-O analysis. It’s also handy for tiny or nearly-sorted arrays.

Common mistakes

• Running the inner loop to n−1 every time instead of n−1−i (still correct, just wasted work).
• Accessing a[j+1] when j = n−1 — an out-of-bounds bug.
• Forgetting to reset swapped = False at the start of each pass.