Tracing rules and trade-offs
Comparison counts, the mid-rounding convention, choosing a search.
Tracing rules the exam drills:
Selection sort pass k: (1) scan from index k to the end for the minimum,
(2) one swap at the end. Comparisons in a pass: n - k - 1. Total swaps:
exactly n − 1 (or fewer if an element swaps with itself — usually counted as
n − 1 passes).
Insertion sort: element k is inserted into the sorted prefix 0..k−1. The number of shifts for element k equals the number of prefix elements greater than it. A sorted array does zero shifts (fast); a reverse-sorted array does the maximum.
Binary search on even-length ranges: mid = (lo + hi) / 2 rounds down,
so for lo=0, hi=3, mid=1 (the left middle). The exam expects you to use
exactly this convention.
When to use which search: data sorted → binary search; unsorted or tiny → linear. Searching an unsorted array with binary search silently returns wrong answers — not an error, which is exactly what makes the multiple-choice version dangerous.