About Bubble Sort
Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through the array, compares adjacent elements, and swaps them if they are in the wrong order. After each full pass, the largest unsorted element 'bubbles up' to its correct position. The algorithm terminates early if a pass completes with no swaps, indicating the array is already sorted. While its O(n²) worst-case performance makes it impractical for large datasets, Bubble Sort is an excellent educational algorithm for understanding sorting fundamentals, invariants, and optimization techniques like early termination.
Complexity Analysis
- Time Complexity
- O(n²)
- Space Complexity
- O(1)
- Difficulty
- beginner
Key Concepts
Bubbling Up
In each pass, the largest unsorted element 'bubbles up' to its correct position at the end of the unsorted portion. After pass p, the element at index N-1-p is in its final sorted position.
Early Termination
If a complete pass makes no swaps, the array is already sorted. This optimization reduces the best-case time complexity from O(n²) to O(n) for already-sorted arrays.
Stability
Bubble Sort is a stable sorting algorithm. Equal elements are never swapped (we use strict > comparison), so their relative order from the original array is preserved.
Adaptive Behavior
Bubble Sort is adaptive — it performs fewer operations on nearly-sorted arrays. The number of swaps equals the number of inversions in the input, and early termination can skip unnecessary passes.
Common Pitfalls
O(n²) worst case
A reverse-sorted array requires the maximum number of comparisons and swaps: n(n-1)/2. For large arrays, this makes Bubble Sort impractical compared to O(n log n) algorithms like Merge Sort or Quick Sort.
Forgetting early termination
Without the swapped flag, Bubble Sort always runs all n-1 passes even on a sorted array. The early termination optimization is simple to implement and dramatically improves best-case performance.
Using >= instead of >
Using >= for comparison instead of > breaks stability. Equal elements would be swapped unnecessarily, changing their relative order from the original array.