How sorting works: bubble and selection

Bubble sort: the teaching sort

Bubble sort is the simplest sorting algorithm to understand, and understanding it teaches you how to reason about sorts.

The idea: sweep left to right, comparing each adjacent pair. If the pair is out of order, swap it. One full sweep is a pass. After the first pass, the largest value has "bubbled" all the way to the end, so the next pass can stop one cell earlier.

Repeat until a pass makes zero swaps, which means the list is sorted.

Nobody ships bubble sort (it is O(n²)), but interviewers still ask you to explain it, and its pass-by-pass trace is the clearest picture of what sorting actually does.

Selection sort: the other O(n²) classic

Selection sort reaches the same sorted result with a different move. Instead of swapping neighbors, it selects the right value for each position directly: find the smallest value in the whole list and swap it into position 0. Find the smallest of what remains and swap it into position 1. Repeat until every position is filled.

Two facts worth knowing before you write it below:

• It always does about n²/2 comparisons — even on an already-sorted list — because "find the smallest of the rest" must scan the rest every single time. Bubble sort's zero-swap early exit beats it on nearly-sorted data.
• It never does more than n swaps (at most one per position). That mattered historically when a swap was expensive — moving a large record on a slow disk — while bubble sort can make O(n²) swaps.

Interviewers pair these two sorts because comparing them forces the real question: what does each pass actually guarantee? A bubble pass guarantees the largest value reaches the end; a selection pass guarantees the smallest values are locked in at the front.