4.15 Sorting Algorithms

What you need to know

• Selection sort: for each position i from 0, find the smallest element in the unsorted part (i to end) and swap it into position i. After k passes, the first k elements are the k smallest, in order.
• Selection sort always does the same number of comparisons regardless of input order: about n²/2. It does at most n − 1 swaps.
• Insertion sort: for each element from index 1 onward, shift it left past larger elements until it's in place among the already-sorted prefix. After k passes, the first k + 1 elements are sorted relative to each other (but may not be the k + 1 smallest overall).
• Insertion sort is fast on nearly-sorted data (few shifts) and slow on reverse-sorted data (many shifts).
• The exam shows an array after some number of passes and asks which algorithm produced it, or asks for the array state after a given pass.
• Both are O(n²) in the worst case; merge sort (4.17) is faster for large inputs.

Worked example

Sort {5, 2, 8, 1, 9}:

Tell-tale: after pass k, selection has the k smallest at the front; insertion has the first k + 1 in order but not necessarily the smallest.

Going deeper

The nuance, edge cases, and connections that turn a 3 into a 5.

• Selection sort, pass i: scan positions i through end, find the index of the minimum, swap it into position i. After pass i, positions 0..i hold the i+1 smallest values in order. Exactly one swap per pass (or zero if the minimum is already there).
• Insertion sort, pass i: take element i, move it left past larger elements until it's in place among 0..i. After pass i, positions 0..i are sorted relative to each other — but a smaller value may still exist later in the array.
• Identifying from a snapshot: if the sorted prefix consists of the globally smallest values → selection. If the prefix is sorted but some later element is smaller than something in the prefix → insertion.
• Work: selection always does ~n²/2 comparisons regardless of input, and at most n−1 swaps. Insertion does few shifts on nearly-sorted input and ~n²/2 on reverse-sorted. So insertion is faster on nearly-sorted data; selection does fewer writes.
• Both are stable in the sense the exam cares about: they sort in place, need no extra array, and are O(n²). Merge sort (4.17) is O(n log n) but needs extra space.
• Sorting Strings or objects uses compareTo or an accessor in the comparison — the algorithm doesn't change.
• Descending order: flip the comparison. Everything else identical.
• You don't write these on the exam; you trace them and identify them. But knowing the mechanics well enough to reproduce a pass is what tracing requires.

Mistakes that cost points

• Confusing the two from a mid-sort array. Check whether the prefix has the smallest values overall.
• Thinking selection sort swaps every pass. Only if the min isn't already in place.
• Assuming insertion sort's prefix has the smallest values. It's sorted, not minimal.

Practice questions

Written in the style of the real exam. Try each one before revealing the answer.