Bubble sort
The simplest sort, and a clean derivation of why it's quadratic. · 6 min read
Bubble sort is the friendliest algorithm to learn first. You walk the array comparing each pair of neighbours, swapping them if they're out of order. After one full pass the largest value has bubbled to the end. Repeat, and the sorted region grows from the right.
Interactive visualization: Bubble sort, step by step — step through it frame by frame on this page.
Watch the code panel: the highlighted line tells you exactly where you are in the loop. When a whole pass makes no swaps, the array is already sorted and we stop early — that's the swapped flag.
Deriving the cost
Pass 1 compares n−1 pairs, pass 2 compares n−2, and so on, because each pass locks one more element at the end. Add them up:
(n−1) + (n−2) + … + 1— Comparisons per pass, shrinking by one each time.= n(n−1) / 2— Sum of the first n−1 integers.≈ ½n²— Drop the lower-order term and the constant.
Result: O(n²)
Interactive visualization: Why those comparisons total ≈ ½n² — step through it frame by frame on this page.