skip to content

Selection sort or bubble sort for 8 records in flash memory, where each swap costs a write?

level: seniorimportance: nice to knowfreq 28%

answer

  1. which operation actually costs here
  2. the shared label counts comparisons only
  3. count writes, not comparisons
  4. one swap per pass versus one per inversion
  5. seven guaranteed writes against twenty-eight

basics

~10 s

Selection sort. It performs at most n-1 swaps whatever the input — 7 writes for 8 records — while bubble sort swaps once per inversion, up to 28. Comparisons are cheap reads here.

solid answer

~50 s

Selection sort, and the reason is that the shared O(n^2) label describes the comparison count, not the operation that actually costs money on this device. Selection sort does one swap per pass — at most n-1 = 7 for eight records, input-independent. Bubble sort swaps once per inversion, so a badly ordered set costs up to n(n-1)/2 = 28 writes, four times as many, on a medium with limited erase-write endurance. Comparisons are reads from a cheap medium and effectively free by comparison. At n=8 nothing asymptotic matters at all; what matters is picking the cost model that matches the hardware. If the write budget is tighter still, the better answer is to sort an index array in volatile memory and commit the final arrangement in one pass of n writes, which also avoids leaving persistent storage in a half-sorted state if power drops mid-sort.

go deeper

for a junior

Know the two swap counts: selection sort swaps once per pass, bubble sort once per out-of-order pair. That single fact answers the question before any complexity argument.

for a middle

Explain that the shared quadratic label counts comparisons, and put numbers on the difference — at most 7 writes against up to 28 for eight records.

for a senior

Demonstrate that you match the cost model to the hardware: writes are the scarce, wear-limited operation, n is fixed and tiny, and sorting in volatile memory with one commit pass beats tuning either loop.

for a principal

Own the constraint conversation — what the device's write budget is, whether persistent state may ever be left half-permuted, and whether an unfamiliar minimal-write algorithm is worth the maintenance burden it puts on the team.

## The question behind the question The skeptic's line — "they are both O(n^2), so it does not matter" — is the misconception this scenario is built to expose. Asymptotic notation classifies growth in a chosen cost unit. For sorting, the conventional unit is the *comparison*, because on ordinary in-memory data comparisons and moves cost roughly the same and comparisons are the ones you cannot avoid. On this device that convention is simply wrong: a comparison is a read from a cheap medium, and a swap is two writes to a medium that is slow, energy-hungry and finite in erase cycles. Change the cost unit and the two algorithms stop being equivalent. ## The numbers for n = 8 | | comparisons | swaps / writes | |---|---|---| | selection sort | 28 (always) | at most 7, input-independent | | bubble sort | up to 28 | equal to the inversion count, up to 28 | Selection sort's swap count is not merely a better bound, it is a *guaranteed* bound: n-1 regardless of the input, and fewer still if you skip the no-op when the minimum already sits at the boundary. Bubble sort's swap count equals the number of inversions in the input — cheap on nearly-ordered data, four times worse on badly ordered data, and you do not control which one arrives. At n = 8 both algorithms complete in a trivially small number of operations, so the entire decision is the write count. This is the concrete case for the general rule: *asymptotics say nothing at small n, where constants and the choice of cost unit decide everything.* ## Defending it to the skeptic Three points, in this order: 1. **Big-O is a bound on a chosen unit.** Both are quadratic in comparisons. In writes, selection sort is linear and bubble sort is quadratic — a whole factor of n apart. That difference is invisible in the label everyone quoted. 2. **The unit that matters here is writes**, because the medium wears out and the write latency dominates the loop by orders of magnitude. Config records that are rewritten on every device boot make the endurance argument real rather than theoretical. 3. **n is fixed and tiny**, so no asymptotic argument for a smarter algorithm applies. A logarithmic-factor sort would add code size and, more importantly, would not obviously write less. ## The better answer, if you are allowed to change more than the algorithm Sorting in place on the persistent medium is itself the questionable decision. Two improvements dominate the bubble-versus-selection choice: - **Sort a copy in volatile memory, then write once.** Read the eight records, sort them in RAM by whatever algorithm you like, and write the final arrangement back. That is at most n writes, and only for records whose position actually changed. - **Make the commit atomic.** In-place sorting on persistent storage means that a power loss mid-sort leaves records in a half-permuted state that is neither the old order nor the new one. A single write-out pass, or a write to a shadow region followed by a pointer flip, makes the operation recoverable. On a device that can lose power at any instant, that is a stronger argument than the write count. If writes must be minimised and the sort must be in place, the algorithm that actually minimises them is cycle sort: it writes each element at most once, achieving the theoretical minimum number of writes, at the price of more comparisons and noticeably trickier code. Reach for it only when the write budget genuinely justifies the maintenance cost of an unfamiliar algorithm — which for eight records it usually does not. ## What the interviewer is grading Not the algorithm choice, which is easy, but whether you (a) noticed that the standard cost model does not apply, (b) can quantify the difference rather than gesture at it, and (c) know when to stop optimising the algorithm and change the design instead. Candidates who answer "selection sort, fewer swaps" and stop have the right answer with none of the reasoning; candidates who reach immediately for an efficient general-purpose sort have missed that n is eight. ## Common wrong answers - "Both quadratic, so flip a coin." Ignores that the quadratic label is about comparisons. - "Bubble sort is fine, the early-exit flag caps the writes." Early exit cuts *passes*, not the inversion count; badly ordered input still costs its full inversion count in swaps. - "Use a divide-and-conquer sort, it is asymptotically better." At n = 8 that argument carries no weight, and it does not reduce writes. - "Comparisons and swaps both cost one unit." That is the convention this scenario deliberately breaks.

  • The skeptic insists both are O(n^2) so the choice is arbitrary. Answer him.
    Big-O bounds growth in a chosen cost unit, and the conventional unit for sorting is the comparison. Measured in writes, selection sort is linear at n-1 and bubble sort is quadratic at one per inversion — a factor of n apart, invisible in the shared label. With n fixed at eight, the compute is negligible and the write count is the entire decision.
  • Does selection sort's write count depend on the input?
    No. It performs exactly n-1 swaps in the plain formulation, whatever the starting order, and fewer only if you skip the no-op when the minimum already sits at the boundary. That input-independence is worth stating: it gives a hard bound for a wear budget, unlike bubble sort's count, which tracks the inversion count of whatever data arrives.
  • How would you cut the writes further if the budget demanded it?
    Read the records into volatile memory, sort them there, and write back only the positions that changed — at most n writes, and the sort algorithm becomes irrelevant. It also makes the update recoverable: a single commit pass, or a shadow region plus a pointer flip, avoids leaving persistent storage half-permuted if power drops mid-sort.
  • Is there an algorithm that writes even less in place?
    Cycle sort writes each element at most once, which is the theoretical minimum number of writes, while paying more comparisons and being distinctly harder to read and review. It is the right answer when a wear budget is the binding constraint; for eight config records the extra maintenance cost rarely justifies it.

saying these in an interview costs you the question

  • Says both are O(n^2) so the choice is arbitrary
  • Counts comparisons as the cost on write-limited storage
  • Argues for an asymptotically faster sort at n equals eight
  • Thinks the early-exit flag bounds bubble sort's write count
  • Never mentions leaving storage half-sorted on power loss

context

resolving links…