Quadratic Sorts: Bubble and Insertion
Two sorting methods that work by comparing neighbouring values, one bubbling the largest to the end each pass and one placing each value into an already sorted front. Both do work proportional to n squared, which is where big-O first bites.
What a learner can do afterwards
- Trace one full pass of bubble sort and one insertion step on the same six values
- Count the comparisons each method makes and match the count to O(n squared)
- Say when insertion sort beats bubble sort, and what nearly sorted input does to each
1 · Read
Bubble sort works by comparing neighbouring values. One pass walks along the list swapping any pair that sits out of order, so the largest value bubbles to the end. Repeat passes until no swaps are needed, and the list stands sorted.
Insertion sort builds the sorted part from left to right. Each step takes the next value and slides it into its correct slot among the values already sorted, shifting bigger ones along. Picture a card player slotting each dealt card into a sorted hand.
Trace both on the same six values in the worst case. Insertion compares the newcomer against all placed cards: 5 + 4 + 3 + 2 + 1 makes 15 comparisons. Bubble does a similar total. Both methods are O(n squared) because their comparison counts grow with the square of n: each of n items can meet n others, so doubling the list roughly quadruples the work.
Insertion beats bubble on nearly sorted input, where each value slots in almost at once and the method runs in nearly linear time. Bubble can only quit early with an early exit flag that stops it after a pass with no swaps; without that check it still grinds through all passes. When asked which is faster, always name the input shape first.
Trace one pass, count the comparisons, feel the square.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.