Two sorts
Insertion can stop early. Selection has to look at every remaining cell.
You sort a hand of cards by keeping a sorted region on the left and sliding the next card into its hole. That is insertion sort. Selection sort does not slide. Each pass scans the unsorted suffix, finds a minimum, and swaps it to the wall. The prefix is not merely sorted. It is finished.
| Insertion | Selection | |
|---|---|---|
| Indexing in the notes | \(1..n\), outer \(j = 2..n\) | \(0..N-1\), outer \(k = 0..N-2\) |
| Prefix means | the original prefix, sorted | the smallest \(k\) values, sorted |
| Suffix | not yet examined | everything left is \(\ge\) the prefix |
| Inner loop | stops when the hole is found | always scans the whole suffix |
| Best case | sorted input, \(\Theta(n)\) | none |
| Worst case | reversed, \(\Theta(n^2)\) | every input, \(\Theta(N^2)\) |
| Exit value | \(j = n+1\) | \(k = N-1\) |
If a question uses 0-based insertion sort, do not quote \(j = n+1\) from memory. Re-derive the exit from the test that is actually written. The idea of the invariant survives a change of indexing. The exit number does not.
Insertion sort
Let \(t_j\) be the number of times the inner while-test is evaluated during outer iteration \(j\), for \(j = 2,\ldots,n\).
- Already sorted: the test fails immediately. \(t_j = 1\). Total inner tests \(n-1\). Best case \(\Theta(n)\).
- Reverse sorted: every new key is smaller than the entire prefix, so the loop shifts all \(j-1\) elements and then fails when \(i\) hits 0. \(t_j = j\).
\[ \sum_{j=2}^{n} j = \frac{n(n+1)}{2} - 1 = \Theta(n^2). \]
Outer invariant. At the start of iteration \(j\), \(A[1..j-1]\) holds the same elements that were originally there, now sorted.
Initialization at \(j = 2\) is one element. Maintenance is the inner loop dropping key into the unique hole. Termination: a for j = 2 to n exits with \(j = n+1\), so \(A[1..n]\) is the original array, sorted.
Selection sort
The course code is 0-indexed, and the comparison is <=. On a tie, mi moves to the later index. mi has to be an index because the swap needs a location. A bare minimum value cannot tell you where to put the old \(A[k]\).
The inner bounds are \(j = k+1,\ldots,N-1\). That is \(N-1-k\) comparisons, decided by \(N\) and \(k\), never by the values. There is no break. Every input pays
\[ \sum_{k=0}^{N-2} (N-1-k) = \frac{N(N-1)}{2} \]
comparisons. Best, worst, and average are the same: \(\Theta(N^2)\).
Invariant, three clauses, at each outer test:
- \(A[0..k-1]\) is sorted.
- Every element of that prefix is \(\le\) every element of \(A[k..N-1]\).
- \(A\) is a permutation of the original array.
Clause (i) alone is the insertion invariant, and it is the wrong invariant here. Clause (ii) is what makes the prefix final. Without it you cannot force the last cell to be the maximum when the loop exits at \(k = N-1\).
Initialization at \(k = 0\) is the empty prefix. Maintenance: the inner loop’s minimum swaps into \(A[k]\), the prefix grows by one finished cell, and k++ restores the wording. Termination: \(k\) rises by exactly 1, so the test \(k < N-1\) fails at \(k = N-1\). There is no pass for the last index. For \(N = 0\) the test \(0 < -1\) fails immediately.
Try the preset “Two 2s” on the picture above and watch mi move on the tie. Then switch to Insertion on “5, 2, 4, 6, 1” and read \(t_j\) off the steps. The sum of those \(t_j\) values is 10. Best case for \(n = 5\) is 4. Worst case is 14. That input sits between them.