1. One-Liner
Bubble Sort repeatedly scans the array, compares adjacent pairs, and swaps them if they are out of order until a pass makes no swaps.
2. The Problem It Solves
You need a very simple, in-place comparison sort for tiny inputs or teaching. It is not used for large production datasets, but it clearly shows how local swaps can globally order data.
3. The Core Idea
Picture bubbles rising: each pass lets the largest unsorted value “float” to the end of the range, like the heaviest bubble reaching the surface last.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Outer pass | For each ending index from n-1 down, walk the unsorted prefix |
| 2. Inner scan | Compare a[j] and a[j+1]; swap if a[j] > a[j+1] |
| 3. Early exit | If a full pass performs no swaps, stop — array is sorted |
| 4. Repeat | Shrink the unsorted suffix each pass |
5. Dry Run Example
Start: [5, 1, 4, 2]. Pass 1 pushes 5 right → [1, 4, 2, 5]. Pass 2 fixes 4 → [1, 2, 4, 5]. Next pass makes no swaps → done.
6. Key Properties
| Property | Value |
|---|---|
| In-place | Yes — O(1) extra |
| Stable | Yes with > (strict) swaps |
| Adaptive | Best O(n) when already sorted + early exit |
7. Where It Is Used
| Company / System | How They Use It |
|---|---|
| Education | Introductory sorting lessons |
| Interviews | Baseline to contrast with faster sorts |
8. Interview Tips
Emphasize O(n²) from nested loops, optional adaptive best case, and that Insertion or Merge are preferred for real data.
9. Comparison with Other Algorithms
| Algorithm | Time (typical) | Space | Stable |
|---|---|---|---|
| Bubble Sort | O(n²) | O(1) | Yes |
| Insertion Sort | O(n²) worst | O(1) | Yes |
| Merge Sort | O(n log n) | O(n) | Yes |
10. Complexity
| Metric | Value |
|---|---|
| Time (Best) | O(n) with early termination |
| Time (Average) | O(n²) |
| Time (Worst) | O(n²) |
| Space | O(1) auxiliary |
| Stable? | Yes |
Implementation Example (PYTHON)
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr