Adjacent swaps propagate the largest element rightward
Bubble sort repeatedly scans the array, comparing adjacent pairs and swapping if out of order. After the first pass, the largest element has bubbled to the end. After the second pass, the second-largest is in its final position. After n-1 passes, the array is sorted. Each pass takes O(n) time, giving O(n^2) total. The algorithm is rarely used in practice because faster sorts exist, but it remains pedagogically useful for learning loop structure and sorting invariants.
Optimization and the concept of comparison-based sorting
A small optimization: after each pass, one fewer comparison is needed (since we know the last k elements are in final position). A bigger optimization: stop early if a pass makes no swaps (the array is sorted). Despite these tweaks, bubble sort remains O(n^2) in the worst case. It illustrates a fundamental fact about comparison-based sorts: you cannot do better than O(n log n) for the general case because you must resolve O(n log n) bits of ordering information through comparisons.