Micro-questions over the elementary sorts module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Why learn three quadratic sorts
1. Give the three reasons.
Answer
- They are the sorts you can prove correct on paper in a minute, using an invariant — a skill that transfers to harder algorithms.
- They differ on properties that matter more than asymptotics on small inputs.
- Insertion sort is genuinely in production — Timsort and introsort both fall back to it below about 16 elements.
2. State the general point about constants.
Answer
Asymptotic notation deliberately discards constants. On small inputs the constants are the whole story.
3. What is an invariant?
Answer
A statement true before and after every iteration. It is what makes a loop provably correct rather than plausibly correct.
B. Selection sort
4. State its invariant.
Answer
After passes, the first positions hold the smallest elements, in order.
5. Describe the mechanism.
Answer
Scan the unsorted remainder for the minimum, swap it into place, repeat.
6. How many comparisons, and why can it not adapt?
Answer
Always — it always scans the whole remainder, so sortedness of the input buys it nothing.
7. How many writes, and why is that its one real advantage?
Answer
Exactly swaps. When a write is far more expensive than a read — flash memory, huge records — it moves the least data of any of these.
8. Is it stable?
Answer
No — the long-range swap can jump one equal element past another.
C. Bubble sort
9. State its invariant.
Answer
After passes, the last positions hold the largest elements, in order.
10. Describe the mechanism.
Answer
Repeatedly sweep, swapping adjacent out-of-order pairs; the largest “bubbles” to the end each pass.
11. What makes it adaptive, and what happens without that?
Answer
An early exit when a pass makes no swaps, giving on sorted input. Without the swapped flag it is even on sorted input, losing the one property that makes it tolerable.
12. Is it stable, and why?
Answer
Yes — it only ever swaps adjacent out-of-order elements, never equal ones.
13. What is its overall verdict?
Answer
The worst of the three — comparisons and writes.
D. Insertion sort
14. State its invariant, precisely.
Answer
After steps, the first elements are sorted among themselves — though not necessarily in final position.
15. Describe the mechanism.
Answer
Take the next element, shift larger elements right, drop it into the gap. Exactly how you sort a hand of cards.
16. What is its cost on nearly-sorted input?
Answer
— and in general where is the number of inversions. The most adaptive of the three.
17. Why is it stable, and what one-character change breaks that?
Answer
It shifts only strictly greater elements. Writing <= instead of < in the shift test shifts equal elements too and destroys stability.
E. Why insertion sort wins small
18. Count the work at for each.
Answer
Merge sort: ~33 comparisons plus allocation, recursive call overhead, and copying to and from temporaries. Insertion sort: at most 45 comparisons, no allocation, no recursion, perfectly sequential memory access.
19. State the conclusion.
Answer
The asymptotics say merge sort wins; the constants say otherwise — and at the constants are all there is.
20. Where is the crossover, and what follows from it?
Answer
Usually between 10 and 32 elements. That is why every serious library is a hybrid.
21. How does each hybrid use it?
Answer
Timsort sorts short runs with binary insertion sort, then merges them. Introsort quicksorts until partitions are small, then finishes the whole array with one insertion-sort pass.
F. Prediction drill
22. On 1,000 already-sorted elements, roughly how many comparisons does each do?
Answer
Selection: ~500,000 (it cannot adapt). Bubble with early exit: ~1,000 (one clean pass). Insertion: ~1,000 (each element compares once and stops).
23. And on the same array reversed?
Answer
All three do about ~500,000 — the reversed array is the worst case for every one of them.
G. Traps
24. Does mean “never use it”?
Answer
No. For these beat everything, which is why they are in the libraries.
25. When should you choose selection sort?
Answer
Only when writes are the expensive operation. It is the slowest in comparisons and cannot adapt.
26. Distinguish swaps from writes.
Answer
One swap is two writes. Selection sort’s swaps are writes.
27. Summarise the three in one sentence.
Answer
All quadratic and all provable in a minute — selection minimises writes, bubble is adaptive only with its early exit, and insertion is adaptive, stable, and the one that survives inside real libraries.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
Software engineering
Infrastructure & security
Computer science
Hardware & engineering