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
  1. They are the sorts you can prove correct on paper in a minute, using an invariant — a skill that transfers to harder algorithms.
  2. They differ on properties that matter more than asymptotics on small inputs.
  3. 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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Sorting