Bubble sort and selection sort are both O(n^2) — what does one pass of each accomplish?
answer
- each pass finalises exactly one element
- one algorithm looks, the other moves
- adjacent exchange versus scan-then-place
- count the swaps inside a single pass
- which end does each pass finalise
basics
~10 sA bubble sort pass swaps out-of-order adjacent pairs, carrying the largest remaining value to the end. A selection sort pass scans the unsorted region for its minimum and places it with one swap.
solid answer
~40 sBoth grow a sorted region one element per pass, but they get there differently. Bubble sort walks the unsorted prefix comparing each neighbouring pair `a[j]` and `a[j+1]`, swapping whenever they are out of order; the effect is that the largest remaining value is carried to the right end of the pass, and many swaps can happen along the way. Selection sort does the opposite split of work: it scans the whole unsorted region doing only comparisons, remembers the index of the minimum, and performs exactly one swap at the end of the pass to move that minimum to the region boundary. Comparison counts are the same — about n(n-1)/2 for a full run — but data movement is not: bubble sort performs one swap per inversion, selection sort at most n-1 swaps in total.
go deeper
Be ready to describe each pass in one sentence and say which end of the array becomes final. Mixing the two mechanics up is the mistake screeners are listening for.
Explain the invariant precisely — what is guaranteed after k passes — and give the comparison and swap counts for each algorithm rather than just the shared O(n^2) label.
Show that you read the cost model, not the label: identical comparison counts, swap counts differing by a factor of n, and what that means when writes are the expensive operation.
Own the framing question: when a team argues about two algorithms in the same complexity class, the useful move is to ask which operation actually costs, and to say so before anyone benchmarks.
## The shape both algorithms share Both sorts maintain a **sorted region** that grows by exactly one element per pass and an unsorted region that shrinks by one. After k passes, k elements are in their final positions and never move again. Both therefore run n-1 passes and land in the same asymptotic class, O(n^2) comparisons. What differs is *which* element gets finalised each pass and *how much data movement* it takes to finalise it. ## One pass of bubble sort Bubble sort scans left to right over the still-unsorted prefix and compares each adjacent pair: ``` for j in 0..n-2-i if a[j] > a[j+1] swap(a[j], a[j+1]) ``` The comparison is always between **neighbours**, and the swap is always between neighbours. The consequence is a one-way ratchet: whenever the scan is holding a large value, it keeps winning comparisons and keeps being pushed right, so it can travel the entire length of the pass in that single pass. A small value, by contrast, moves left by **at most one position per pass** — it only moves when the scan happens to compare it with its immediate left neighbour, and after that the scan has moved past it. So the guarantee after pass i is: the last i+1 slots hold the i+1 largest values, in final order. That asymmetry (large values fly right, small values crawl left) is the single most useful fact about the algorithm, and it explains both its behaviour on partly ordered data and why the naive "it's symmetric" intuition is wrong. Swap count: bubble sort swaps exactly once for every **inversion** — every pair of positions that starts out in the wrong relative order. A reversed input has n(n-1)/2 inversions, so a reversed input costs n(n-1)/2 swaps. ## One pass of selection sort Selection sort separates looking from moving: ``` m = i for j in i+1..n-1 if a[j] < a[m] m = j swap(a[i], a[m]) ``` The inner loop performs comparisons only, tracking the index of the smallest value seen. Nothing in the array moves during the scan. At the very end, one swap puts the minimum at position i — and that swap can be **long-range**, exchanging two elements that are far apart. The guarantee after pass i is the mirror image of bubble sort's: the first i+1 slots hold the i+1 smallest values, in final order. Nothing at all is known about the arrangement of the remaining region — unlike bubble sort, where the tail of the unsorted region has also been partially nudged toward order. Swap count: exactly n-1 in the plain formulation (or fewer if you skip the no-op when the minimum is already at the boundary). This is **independent of the input** — sorted, reversed, or random, selection sort writes the same amount. ## The counts side by side | | comparisons | swaps (worst) | swaps (best) | |---|---|---|---| | bubble (no early exit) | n(n-1)/2 | n(n-1)/2 | 0 | | selection | n(n-1)/2 | n-1 | n-1 (or 0 with the skip) | Read that table carefully: the shared O(n^2) label is a statement about the **comparison** count. The number of writes differs by a whole factor of n. On ordinary in-memory data that difference is a constant-factor curiosity; where a write is expensive — persistent storage, wear-limited memory, large records copied by value — it is the whole story. ## What interviewers are actually checking They want to hear that you can describe an invariant rather than recite a name. "Bubble sort bubbles things up" is not an answer; "after k passes the last k slots hold the k largest values in final order, because each pass carries the running maximum rightward through adjacent swaps" is. The same for selection sort: the pass is a scan plus one placement, and that placement is a swap over an arbitrary distance. ## Common wrong answers - Saying bubble sort "finds the smallest and moves it to the front" — that is selection sort's shape, and mixing them up is the most common junior error. - Claiming both do the same amount of data movement because both are O(n^2). - Asserting that a single element can only move one slot per bubble pass. Small values crawl; large values can cross the whole pass. - Believing selection sort's single swap makes it harmless to substitute anywhere: that long-range swap has a real consequence for records that compare equal.
- After k passes, what can you assert about the array in each case?For bubble sort ascending, the last k slots hold the k largest values in final order; the rest is partly nudged toward order. For selection sort, the first k slots hold the k smallest values in final order, and nothing at all is known about the arrangement of the remaining region.
- Do the two do the same number of comparisons?Yes — both perform n(n-1)/2 comparisons for a full run, which is why they share the O(n^2) label. Selection sort's count is fixed no matter what the input looks like; bubble sort's drops only if you add an early-exit check that stops once a pass makes no swaps.
- In one bubble sort pass, how far can a single element travel?A large value can travel all the way to the end of the pass, because the scan keeps carrying it right. A small value moves left by at most one position per pass, since once the scan passes it, it is not compared again until the next pass.
Bubble sort is nudging the heaviest box one shelf at a time down a row until it reaches the end. Selection sort is walking the whole row first, then carrying the single lightest box straight to the front.
saying these in an interview costs you the question
- Says bubble sort finds the minimum each pass
- Claims selection sort swaps adjacent elements
- Thinks both perform the same number of swaps
- Assumes every element moves at most one slot per bubble pass
- Cannot state what a completed pass guarantees