4.15 Sorting Algorithms

4.15 Sorting Algorithms

A sorting algorithm rearranges a collection into a chosen order, such as smallest to largest. The central question is not merely whether the values become ordered, but how the algorithm moves through the collection and what work it repeats.

Two ways to build order

Imagine organizing library books by height. Selection sort repeatedly searches the unsorted portion for the smallest remaining book, then places it at the next open position. Insertion sort treats the left portion as already organized and inserts each new book into its correct location.

Algorithm	Main idea	What becomes correct after one major step?
Selection sort	Find the smallest value in the unsorted region and swap it into position	One position at the front is permanently correct
Insertion sort	Remove the next value and shift larger values right until the value fits	A larger sorted prefix is created

Both algorithms are comparison-based: they decide where values belong by comparing pairs of values. Their typical running time is $O(n^2)$ because an array of $n$ values may require a number of comparisons proportional to $n \times n$.

Selection sort: choose, then swap

For each position start, selection sort searches from start through the end of the array. It records the index of the smallest value found, then swaps that value with the value currently at start.

public static void selectionSort(int[] values) {
    for (int start = 0; start < values.length - 1; start++) {
        int minIndex = start;

        for (int index = start + 1; index < values.length; index++) {
            if (values[index] < values[minIndex]) {
                minIndex = index;
            }
        }

        int temporary = values[start];
        values[start] = values[minIndex];
        values[minIndex] = temporary;
    }
}

Worked trace. Start with [7, 2, 6, 4].

1. At start = 0, the smallest value is 2; swap it with 7: [2, 7, 6, 4].
2. At start = 1, the smallest value in [7, 6, 4] is 4: [2, 4, 6, 7].
3. At start = 2, the smallest value in [6, 7] is already 6.

After each outer-loop iteration, one additional position is permanently sorted.

Insertion sort: shift, then insert

Insertion sort begins with the assumption that the first value is sorted. Each later value is called the key. Values in the sorted prefix that are larger than the key shift one position to the right, leaving an opening for the key.

public static void insertionSort(int[] values) {
    for (int start = 1; start < values.length; start++) {
        int key = values[start];
        int position = start - 1;

        while (position >= 0 && values[position] > key) {
            values[position + 1] = values[position];
            position--;
        }

        values[position + 1] = key;
    }
}

Worked trace. Consider [1, 4, 5, 3, 8] while processing the key 3.

• The sorted prefix is [1, 4, 5].
• Since 5 > 3, shift 5 right: [1, 4, 5, 5, 8].
• Since 4 > 3, shift 4 right: [1, 4, 4, 5, 8].
• Since 1 is not greater than 3, stop shifting.
• Insert 3 at index 1: [1, 3, 4, 5, 8].

The key is not copied into its final position until the shifting loop ends.

Correctness, efficiency, and edge cases

A sorting algorithm must preserve every original value while changing only the order. A useful correctness invariant is:

After selection sort finishes iteration start, every position from 0 through start contains the correct smallest values in sorted order.

Insertion sort can be faster than selection sort on an array that is already nearly sorted, because few shifts are needed. However, both algorithms can take $O(n^2)$ time on a reverse-ordered array. A nearly sorted input does not change selection sort's need to search the remaining region, so selection sort still performs many comparisons.

Misconception check — “A sorted prefix means the whole array is sorted.” In insertion sort, only the prefix before the current key is guaranteed to be sorted. The unprocessed suffix may still be in any order.

Misconception check — “Swapping and shifting are interchangeable.” Selection sort generally performs a swap after locating a minimum. Insertion sort shifts larger values to preserve their relative order and creates one opening for the key.

AP skills and retrieval check

Sorting problems assess Computational Thinking Practice 1 — Design Code, when selecting or adapting an algorithm; Computational Thinking Practice 2 — Develop Code, when implementing loop logic and swaps or shifts; and Computational Thinking Practice 3 — Analyze Code, when tracing iterations, identifying invariants, counting operations, and debugging boundary conditions. Computational Thinking Practice 4 — Document Code and Computing Systems applies when comments explain the sorted region or algorithm purpose.

Retrieval check. In insertion sort, process key 3 in [1, 4, 5, 3, 8]. Which values shift, and what is the resulting array?

Answer: 5 shifts right, then 4 shifts right. The result is [1, 3, 4, 5, 8]. No value shifts past 1 because 1 > 3 is false.