Bubble Sort
Scenario
A graphics engine renders polygons by maintaining an Active Edge Table sorted by x-coordinate. As the scanline moves down one pixel, only two adjacent edges may swap order at an intersection.
What sorting algorithm can detect that the list is already nearly sorted and fix the one swap in O(N) time?
Why it exists
Problem: Sorting requires rearranging elements into order. When the data is almost sorted, using a heavy O(N log N) algorithm wastes overhead on recursive calls, auxiliary memory, and pivot selection for a problem that is nearly solved.
Naive approach: Apply a full Merge Sort or Quick Sort regardless of the input's existing order, paying the full O(N log N) cost even when only one element is out of place.
Better idea: Repeatedly compare adjacent pairs and swap them if they are out of order. Large elements 'bubble' to the end. Add an early-exit flag: if a complete pass produces zero swaps, the array is sorted and we stop immediately, achieving O(N) best-case on nearly-sorted data.
Mental model
Imagine bubbles in a glass of water. The largest bubbles rise to the surface first. In each pass through the array, the largest unsorted element floats to its correct position at the end.
The algorithm sweeps through the array from left to right, comparing each element with its immediate right neighbor. If the left element is larger, they are swapped. After each complete pass, the largest unsorted element is guaranteed to be in its final position. Subsequent passes only need to process the shrinking unsorted prefix.
Repeated decision: Is `arr[j] > arr[j+1]`? If yes, swap them.
Explanation
Bubble Sort uses two nested loops. The outer loop runs N-1 times. The inner loop walks through the unsorted portion, comparing adjacent elements.
The key optimization is the `swapped` flag. Before each inner-loop pass, set `swapped = False`. If a swap occurs, set `swapped = True`. After the inner loop, if `swapped` is still `False`, the array is sorted and we break out of the outer loop immediately.
This optimization transforms the best-case (already sorted array) from O(N^2) to O(N), because the first pass performs N-1 comparisons with zero swaps and then halts.
The loop invariant is: after the i-th pass of the outer loop, the last i elements of the array are in their final sorted positions, and every element in this sorted suffix is greater than or equal to every element in the unsorted prefix.
A notable quirk is the 'Rabbit and Turtle' problem. Large values at the beginning ('rabbits') travel to the end quickly, traversing the array in a single pass. But small values at the end ('turtles') move toward the beginning by only one position per pass. A single misplaced small element at the end forces O(N) passes.
Key points
- Adaptive Best-Case: With the `swapped` flag, Bubble Sort detects a sorted array in O(N) time.
- Stable Sort: Only adjacent elements are swapped, so equal elements never leapfrog each other. Relative order is preserved.
- In-Place: O(1) auxiliary space. No extra arrays needed.
Pattern: Adjacent Swap / Adaptive Detection
Recognition cues:
- The data is known to be nearly sorted with only a few elements out of place.
- Stability is required and the dataset is very small.
Failure signals
- You are using Bubble Sort on a large, randomly ordered dataset. Its O(N^2) worst-case is catastrophically slow.
- Profiling reveals the bottleneck is memory writes. Bubble Sort does up to O(N^2) swaps (3 writes each).
Engineering examples
Computer Graphics: Active Edge Tables
Sorting polygon edges by x-coordinate as a scanline advances. The edge order only changes at intersection points.
The data is nearly sorted between scanlines. Bubble Sort detects this in O(N) time and fixes the one or two adjacent swaps instantly.
When not to use
- Large, randomly ordered datasets: Bubble Sort degrades to O(N^2) with poor branch prediction and high memory write overhead, making it far slower than O(N log N) alternatives.
Common mistakes
- Forgetting the `swapped` flag optimization: Without the early-exit flag, Bubble Sort always runs the full N-1 passes even on a sorted array, guaranteeing O(N^2) time.
- Not shrinking the inner loop boundary: After pass i, the last i elements are sorted. The inner loop should only iterate up to N-1-i, not N-1. Failing to do this doubles the number of unnecessary comparisons.
Glossary
- unsorted prefix
- The beginning part of a list that hasn't been organized yet.
- auxiliary space
- Extra temporary memory required by an algorithm beyond the original data.
- early-exit flag
- A specific marker used to stop a process immediately when it's no longer needed.
Recall questions
- What optimization gives Bubble Sort an O(N) best-case?
- What is the loop invariant of Bubble Sort?
- Why is Bubble Sort a stable sorting algorithm?
Questions & answers
Implement Bubble Sort with the early-termination optimization.
Use a nested loop. Before the inner loop, set `swapped = False`. Inside, compare adjacent elements and swap if out of order, setting `swapped = True`. After the inner loop, break if `swapped` is still `False`.
Approach: Optimized Bubble Sort.
Given an array that is already sorted except for one element that is misplaced, sort it in O(N) time.
Use a single pass of Bubble Sort (or Insertion Sort). Both detect the nearly-sorted state and terminate early.
Approach: Adaptive sorting.
Interesting facts
- Former Google CEO Eric Schmidt once asked Barack Obama how to sort a million integers in an interview. Obama correctly replied, 'I think Bubble Sort would be the wrong way to go.'
Continue learning
Previous: In-Place Operations
Next: Insertion Sort
Related: Insertion Sort
Related: Selection Sort