Bubble Sort Explained — How It Works Step by Step
Learn how Bubble Sort works by repeatedly comparing and swapping adjacent elements. Understand its O(n squared) time complexity and when it is still useful.
Detailed Explanation
How Bubble Sort Works
Bubble Sort is the simplest comparison-based sorting algorithm. It repeatedly steps through the array, compares each pair of adjacent elements, and swaps them if they are in the wrong order. This process continues until no more swaps are needed, meaning the array is sorted.
The Algorithm Step by Step
for i = 0 to n-2:
for j = 0 to n-2-i:
if arr[j] > arr[j+1]:
swap(arr[j], arr[j+1])
After each complete pass through the array, the largest unsorted element "bubbles up" to its correct position at the end. This is where the algorithm gets its name.
Pass-by-Pass Example
Consider the array [5, 3, 8, 1, 2]:
- Pass 1: Compare (5,3) swap → (3,8) no swap → (8,1) swap → (8,2) swap →
[3, 5, 1, 2, 8] - Pass 2: (3,5) no → (5,1) swap → (5,2) swap →
[3, 1, 2, 5, 8] - Pass 3: (3,1) swap → (3,2) swap →
[1, 2, 3, 5, 8] - Pass 4: No swaps → array is sorted
Time Complexity Analysis
| Case | Complexity | When |
|---|---|---|
| Best | O(n) | Array is already sorted (with early termination) |
| Average | O(n²) | Random order |
| Worst | O(n²) | Reverse sorted |
The Early Termination Optimization
A key optimization is tracking whether any swap occurred during a pass. If a complete pass makes zero swaps, the array is already sorted and the algorithm can terminate early. This optimization makes the best case O(n) for already-sorted inputs.
Space Complexity
Bubble Sort uses O(1) extra space because it only needs a temporary variable for swapping. It is an in-place and stable sorting algorithm, meaning equal elements maintain their original relative order.
Use Case
Bubble Sort is rarely used in production code due to its O(n squared) average performance. However, it is an excellent teaching tool because its logic is straightforward and easy to visualize. It can also be practical for very small arrays (under 10 elements) or for detecting whether an array is already sorted, since it terminates in O(n) time on sorted input.