College Board Unit 4
How it works
Selection sort finds the smallest remaining element and swaps it into place, so after k passes the first k positions are finalized. Insertion sort grows a sorted prefix by shifting each new element left into position, so after k passes the first k + 1 elements are sorted relative to each other but may still move. Merge sort recursively splits the array, sorts the halves, and merges them, which makes it substantially faster on large inputs.
Compare algorithms by counting comparisons as the input grows, not by timing one run.
Common error
Claiming an algorithm is fast from one small example. Growth rate, not a single measurement, is what is being compared.
Worked example
Java
int[] a = {5,2,4};
int min = 0;
for (int i = 1; i < a.length; i++) {
if (a[i] < a[min]) min = i;
}
int temp = a[0]; a[0] = a[min]; a[min] = temp;
System.out.println(Arrays.toString(a));Output
[2, 5, 4]This is one selection-sort pass, not the full sort. The minimum moves to index 0.
Exercises
8.4.1 · Trace
Determine the exact output. Explain the Java rule or state changes that produce it.
Java
int[] a = {2,5,4};
int key = a[2];
int j = 1;
while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
a[j + 1] = key;
System.out.println(Arrays.toString(a));Show solution
Output
[2, 4, 5]The insertion shifts 5 right, then places 4 after 2.
8.4.2 · Write code
Write public static void selectionSort(int[] values). Sort ascending in place. Explain why doubling a large input size produces approximately four times as many comparisons.
Show solution
One valid solution is shown below. Other implementations satisfying the contract are also valid.
Java
public static void selectionSort(int[] values) {
for (int start = 0; start < values.length - 1; start++) {
int min = start;
for (int i = start + 1; i < values.length; i++) {
if (values[i] < values[min]) min = i;
}
int temp = values[start];
values[start] = values[min];
values[min] = temp;
}
}
// Comparisons: n * (n - 1) / 2; the leading term is proportional to n squared.Check your code
Java
int[] a = {5,2,5,-1}; selectionSort(a); System.out.println(Arrays.toString(a));
int[] b = {}; selectionSort(b); System.out.println(Arrays.toString(b));Expected output
[-1, 2, 5, 5]
[]