Sorting Algorithms

Sorting the Garage

Back in Topic 4.3, the garage just held cars in whatever spot they happened to get parked in. Nobody cared about order — spot 0 could have ticket #145, spot 1 could have ticket #12, total chaos. Sorting is what happens when the manager finally says “line these up by ticket number,” and now the attendant needs an actual strategy for rearranging cars without a second garage to work in.

There are a lot of ways to sort a list. AP CSA only holds you accountable for two: Selection Sort and Insertion Sort. Both rearrange the array in place, and both are worth understanding deeply enough to trace by hand — not because you’ll write one from scratch on exam day, but because you’ll be handed a partially-sorted array and asked what algorithm produced it and what happens next.

Selection Sort: Picking the Best Car Each Round

Imagine the manager walks the entire unsorted section of the garage, finds whichever car has the lowest ticket number anywhere in it, and swaps that car into the very next open sorted spot — even if that means moving it several spaces down the row. Then the manager does the exact same full sweep again, starting one spot further in, ignoring everything already locked into place.

That’s Selection Sort: repeatedly select the smallest remaining element and swap it into position.

Tracing {29, 10, 14, 37, 13}:

Start:            [29, 10, 14, 37, 13]
Pass 1 (i=0):  smallest in [29,10,14,37,13] is 10 → swap with index 0
               → [10, 29, 14, 37, 13]
Pass 2 (i=1):  smallest in [29,14,37,13] is 13 → swap with index 1
               → [10, 13, 14, 37, 29]
Pass 3 (i=2):  smallest in [14,37,29] is 14 → already in place, no swap needed
               → [10, 13, 14, 37, 29]
Pass 4 (i=3):  smallest in [37,29] is 29 → swap with index 3
               → [10, 13, 14, 29, 37]
Done — last element is automatically in place.

The trace above is exactly what the method below executes — the outer loop is each pass, and the inner loop is the “walk the unsorted section looking for the smallest” step:

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

The key thing to notice: the outer loop’s i marks the boundary of the “already sorted” section, and the inner loop only ever looks, tracking minIndex — the actual swap doesn’t happen until the inner loop finishes scanning everything to its right.

Popcorn Hack 1

Trace Selection Sort on {42, 8, 15, 4, 23} by hand. Write out the array’s state after each pass before checking below.

Click to reveal the trace 
Start:            [42, 8, 15, 4, 23]
Pass 1 (i=0):  smallest is 4 → swap with index 0
               → [4, 8, 15, 42, 23]
Pass 2 (i=1):  smallest in [8,15,42,23] is 8 → already in place
               → [4, 8, 15, 42, 23]
Pass 3 (i=2):  smallest in [15,42,23] is 15 → already in place
               → [4, 8, 15, 42, 23]
Pass 4 (i=3):  smallest in [42,23] is 23 → swap with index 3
               → [4, 8, 15, 23, 42]
Done.

Insertion Sort: The Valet Line

Now picture a valet line instead of a garage sweep. Cars pull up one at a time, and the valet already has a perfectly sorted line built up from everyone who arrived earlier. When the next car pulls in, the valet doesn’t re-sort the whole line — they just walk backward from the end of the sorted line, sliding cars over one spot at a time, until they find the exact gap where the new arrival belongs, then slot it in.

That’s Insertion Sort: build a sorted section one element at a time, shifting existing elements over to make room.

Tracing {29, 10, 14, 37, 13}:

Start:                [29, 10, 14, 37, 13]
Insert index 1 (10):  10 < 29, shift 29 right, insert 10
                       → [10, 29, 14, 37, 13]
Insert index 2 (14):  14 < 29, shift 29 right; 14 > 10, stop, insert 14
                       → [10, 14, 29, 37, 13]
Insert index 3 (37):  37 > 29, no shifting needed, stays put
                       → [10, 14, 29, 37, 13]
Insert index 4 (13):  13 < 37, < 29, < 14, shift all three right; 13 > 10, stop, insert 13
                       → [10, 13, 14, 29, 37]
Done.

Compare this method to the trace above line by line — key is the car currently pulling up, and the while loop is the valet walking backward looking for its gap:

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Notice the outer loop starts at i = 1, not 0 — a single car is already “sorted” by default. The while loop is the valet stepping backward through the line, and it stops the moment it finds a car that’s already smaller than the one being placed.

Popcorn Hack 2

Trace Insertion Sort on {42, 8, 15, 4, 23} by hand — same starting array as Popcorn Hack 1. Write out the state after each element gets inserted before checking below.

Click to reveal the trace 
Start:                 [42, 8, 15, 4, 23]
Insert index 1 (8):    8 < 42, shift 42 right, insert 8
                        → [8, 42, 15, 4, 23]
Insert index 2 (15):   15 < 42, shift 42 right; 15 > 8, stop, insert 15
                        → [8, 15, 42, 4, 23]
Insert index 3 (4):    4 < 42, 15, 8 — shift all three right, insert 4 at front
                        → [4, 8, 15, 42, 23]
Insert index 4 (23):   23 < 42, shift 42 right; 23 > 15, stop, insert 23
                        → [4, 8, 15, 23, 42]
Done.

Comparing the Two

Both algorithms end up sorted, both run in O(n²) worst-case time, and both work in place — no second garage required. Where they differ is how they get there, which matters most when the input is already close to sorted:

  Selection Sort Insertion Sort
Strategy Repeatedly find the minimum of what’s left, swap it into place Repeatedly grab the next element, shift sorted elements over to insert it correctly
Number of comparisons Same every time, regardless of starting order Fewer comparisons if the array starts out nearly sorted
Number of swaps/shifts At most one swap per pass Can shift several elements per insertion
Best case Still scans everything — no shortcut Can be close to O(n) if the array is nearly sorted already

Popcorn Hack 3

The array {5, 3, 8, 4, 9} was sorted using one of the two algorithms above. After the second pass, it looks like this:

[3, 5, 8, 4, 9]

Which algorithm produced this, and what will the array look like after the next pass?

Click to reveal the answer

This is Insertion Sort. Selection Sort would have found the true minimum (3) and moved it to index 0 immediately on pass 1 — which did happen here — but on pass 2, Selection Sort would scan everything from index 1 onward for the next smallest value (4) and swap it into index 1. Since index 1 holds 5, not 4, this isn’t Selection Sort’s second pass.

Insertion Sort, on the other hand, only ever compares each new element against the sorted section built so far. After inserting 3 at the front (pass 1) and then inserting 5 right where it already belonged (pass 2, no shifting needed since 5 > 3), the array is exactly [3, 5, 8, 4, 9] — matching what’s given.

Next pass (inserting 4): 4 < 8, shift 8 right; 4 > 3, stop — insert 4. Result: [3, 4, 5, 8, 9]

⚠️ Watch Out

  • Selection Sort only swaps once per pass — the inner loop just tracks minIndex, it doesn’t swap every time it finds something smaller. Forgetting this leads to tracing way more swaps than actually happen.
  • Insertion Sort’s inner loop condition needs both checks — j >= 0 && arr[j] > key. Drop the j >= 0 and it throws an ArrayIndexOutOfBoundsException the moment the smallest element in the array needs to shift all the way to the front.
  • Mixing up which loop variable marks the sorted boundary. In Selection Sort, everything before i is sorted. In Insertion Sort, everything before i is sorted too — but the mechanism for getting the new element into that section is completely different (swap vs. shift), and mixing up the two mid-trace is the single most common exam mistake on this topic.
  • Assuming both algorithms make the same number of moves. They don’t — that’s the whole point of the comparison table above.

References

College Board. (2025). AP Computer Science A course and exam description [Effective fall 2025]. Unit 4: Data Collections, Topic 4.15 Sorting Algorithms (p. 126). https://apcentral.collegeboard.org/media/pdf/ap-computer-science-a-course-and-exam-description-effective-fall-2025.pdf