algorithms · medium

Bubble Sort

Bubble sort repeatedly walks the array swapping adjacent elements that are out of order; after each pass the largest unsorted value settles at the end. It runs in O(n^2) time and O(1) space and is stable. A `swapped` flag lets it stop early — O(n) on already-sorted input — but it's still only suitable for teaching or tiny arrays.

The code

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; ++i) { // up to n-1 passes
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) // last i elements are in place
            if (a[j] > a[j + 1]) {          // adjacent pair out of order?
                std::swap(a[j], a[j + 1]);  // swap them
                swapped = true;
            }
        if (!swapped)
            break; // no swaps -> already sorted
    }
}

What this lesson walks through

1. 01Bubble sort — the unsorted array
2. 02After pass 1
3. 03After pass 2
4. 04After pass 3
5. 05Sorted

Bubble sort walks the array repeatedly, swapping each adjacent pair that's out of order. After every full pass the largest remaining value has 'bubbled' up to the end.