Sorting I: Bubble, Selection & Insertion

Sorting is the "hello world" of algorithms, everyone's first real puzzle in trading speed for simplicity. The three sorts in this lesson are the ones you'd reinvent on your own if nobody had named them: compare things, swap the ones out of order, repeat. They're slow on big inputs, but they're the clearest window into how an algorithm thinks, and that intuition pays off everywhere else.

All three are O(n²), which we'll unpack. First, watch them move.

Bubble sort: swap your way up

Bubble sort is the most literal one. Walk the list left to right, and whenever two neighbors are out of order, swap them. The biggest value "bubbles" to the end on the first pass. Do another pass and the next-biggest settles into place. Keep going until a full pass makes no swaps. That's how you know it's sorted.

Step through it and watch the largest element float to the right on each pass:

Each pass only guarantees one element lands in its final spot (the largest not-yet-placed one), so an n-element list can need close to n passes, each scanning close to n elements. That n passes × n comparisons is exactly where the n² comes from, and you can watch the comparison count climb in the visualizer.

Selection and insertion: two other takes

Selection sort flips bubble's idea around. Instead of repeatedly swapping neighbors, it scans the unsorted part for the single smallest value, then drops it into place at the front. Scan, select the minimum, swap it home, then repeat on the rest. Fewer swaps than bubble (one per pass), but it still scans the whole unsorted region every time, so the comparisons are still n².

Insertion sort is how most people sort a hand of playing cards without thinking about it. Keep the left part of the list sorted, take the next card, and slide it left until it sits in the right spot among the cards you've already placed. On nearly-sorted data it's genuinely fast (each new card barely moves), which is why it quietly powers the small-array case inside real-world sorting libraries.

Pick any of the five from the dropdown and run them on the same array. Watch how bubble swaps constantly, selection scans-then-swaps once per pass, and insertion shuffles each new element back into a sorted left side:

Comparing them side by side is the point. They reach the same sorted result by different routes, and you can see the difference in the swap and comparison counters as they run.

Writing two of them

Here are bubble sort and insertion sort in plain Python. Run it, then feed them your own list:

Both have the giveaway of a quadratic sort: a loop inside a loop, each running on the order of n times. The swapped flag in bubble sort lets it bail early on an already-sorted list (best case O(n)), and insertion sort's inner while stops as soon as the new element fits, which is why nearly-sorted input is its happy path.

If the nested loops here look unfamiliar, they're the same for/while machinery from the Python loops lesson, and the swap a[j], a[j+1] = a[j+1], a[j] is plain tuple assignment.

Where this leaves you

Bubble, selection, and insertion sort are the friendly, slow trio: easy to write, easy to reason about, and all O(n²) because they nest a comparison loop inside a pass loop. They're the right tool for small or nearly-sorted data and the wrong one for large random data.

To beat quadratic time you need a smarter strategy: break the problem in half, sort the halves, and combine. Next: Sorting II: Merge Sort & Quicksort.