Bubble Sort

Sorting O(n²) O(1)

Repeatedly swaps adjacent elements that are out of order, bubbling the largest value to the end on each pass.

Idle

Starting Bubble Sort on 8 elements.

InvariantThe last 0 element(s) are in final position; nothing before them is larger.

1/47

comparisons0swaps0i0j0

compareswapshiftselectsorted

bubble-sort.c

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

How Bubble Sort works

Sweep the array left to right, swapping any adjacent pair that is out of order. Each pass floats the largest remaining value to the end, so the sorted suffix grows by one every pass.

Best case

Already sorted — one pass, no swaps, the swapped flag exits early: O(n).

Worst case

Reverse-sorted input — every pair must be swapped: O(n²) comparisons and swaps.

When to use it

Teaching and tiny inputs only; in practice it is dominated by insertion sort.