Reference Guide

Key Topics

Term Definition Example
Sorting Rearranging elements into order (smallest to largest here). [29, 10, 14] → [10, 14, 29]
In place Sorting inside the same array, no second array needed. Both sorts in this lesson
Pass One run of the outer loop. Selection Sort on 5 elements takes 4 passes
Swap Trading two elements using a temporary variable. temp = a[i]; a[i] = a[m]; a[m] = temp;
Shift Sliding an element one spot right to open a gap. arr[j + 1] = arr[j];
Selection Sort Find the smallest remaining element, swap it into the next sorted spot. Garage manager sweep
Insertion Sort Take the next element, shift bigger sorted elements right, insert it in the gap. Valet line
  • In both algorithms, everything before index i is the sorted section.
  • Selection Sort makes at most one swap per pass. Insertion Sort can make many shifts per insertion.

Selection vs. Insertion

  Selection Sort Insertion Sort
Strategy Find the minimum of what’s left, swap it into place Grab the next element, shift sorted elements over, insert it
Outer loop i from 0 to length - 2 i from 1 to length - 1
Comparisons Same every time, no matter the starting order Fewer when the array starts nearly sorted
Moves At most one swap per pass Can shift several elements per insertion
Already-sorted input Still scans everything One comparison per element

Picking Which Sort Is Running

  • After pass k, the first k spots hold the k smallest values in the whole array → Selection Sort
  • After pass k, the first k + 1 spots are sorted among themselves, but a smaller value may still be waiting to the right → Insertion Sort
  • A small value jumped from far right to the front in one pass → Selection Sort (a swap)
  • A group of values each slid one spot right → Insertion Sort (shifts)

College Board Requirements

AP CSA Unit 4, Topic 4.15 Sorting Algorithms. Summarized from the course and exam description (College Board, 2025, p. 126):

  • Selection Sort and Insertion Sort are iterative sorting algorithms that can be used to sort elements in an array or ArrayList.
  • Selection Sort repeatedly selects the smallest remaining element and swaps it into its correct position.
  • Insertion Sort inserts one element at a time into its correct position among the elements already sorted, shifting other elements to make room.

Big-O notation such as O(n²) is outside the scope of the AP exam. This lesson still mentions it because it is common in real code, but the exam asks you to trace passes and compare how many times statements run instead.

Lesson Plan

Learning Objective: Trace Selection Sort and Insertion Sort and identify which algorithm produced a given partial result.

Success Criteria: You can write the array after every pass of either sort, name the algorithm from a partial trace, and explain which one does less work on nearly sorted data.

Tech Talk

Back in 4.3, cars were parked in whatever spot they landed in. Now the manager says “line them up by ticket number,” and there’s no second garage to work in.

Selection Sort is the manager’s sweep: walk the whole unsorted section, find the lowest ticket, and swap it into the next sorted spot. Insertion Sort is the valet line: each new car pulls up, and the valet walks backward through the already-sorted line, sliding cars over until the gap for the new car appears.

Both are built on moving values around inside one array. Selection Sort uses swaps, Insertion Sort uses shifts.

Code Runner Challenge

Run it, then remove the temp variable from the swap and see what goes wrong

View IPYNB Source
// CODE_RUNNER: Run it, then remove the temp variable from the swap and see what goes wrong
import java.util.Arrays;

public class SwapAndShift {
    public static void main(String[] args) {
        int[] garage = {29, 10, 14, 37, 13};

        // Swap spots 0 and 1 (Selection Sort's move)
        int temp = garage[0];
        garage[0] = garage[1];
        garage[1] = temp;
        System.out.println("After swap:  " + Arrays.toString(garage));

        // Shift spot 3 right by one (Insertion Sort's move)
        int[] line = {10, 14, 29, 37, 13};
        int key = line[4];
        line[4] = line[3];
        System.out.println("After shift: " + Arrays.toString(line) + " (holding " + key + ")");
    }
}

SwapAndShift.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Code Examples

A. Selection Sort. The SelectionTrace class prints the array after every pass

Three parts of each pass get mixed up a lot:

Code Runner Challenge

Predict every pass on paper first, then run it and compare

View IPYNB Source
int minIndex = i;                  // assume the first unsorted spot holds the smallest
if (arr[j] < arr[minIndex])        // the inner loop only looks...
    minIndex = j;                  // ...and remembers where the smallest is
// swap happens once, after the inner loop finishes
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Code Runner Challenge

Predict every insertion on paper first, then run it and compare

View IPYNB Source
// CODE_RUNNER: Predict every pass on paper first, then run it and compare
import java.util.Arrays;

public class SelectionTrace {
    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;
            System.out.println("Pass " + (i + 1) + ": " + Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        int[] tickets = {29, 10, 14, 37, 13};
        System.out.println("Start:  " + Arrays.toString(tickets));
        selectionSort(tickets);
    }
}

SelectionTrace.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...
Click to reveal the trace

Code Runner Challenge

Run it, then try a nearly sorted array like {1, 2, 4, 3, 5} and explain the counts

View IPYNB Source
Start:   [29, 10, 14, 37, 13]
Pass 1:  smallest is 10 → swap with index 0 → [10, 29, 14, 37, 13]
Pass 2:  smallest in [29,14,37,13] is 13 → swap with index 1 → [10, 13, 14, 37, 29]
Pass 3:  smallest in [14,37,29] is 14 → already in place → [10, 13, 14, 37, 29]
Pass 4:  smallest in [37,29] is 29 → swap with index 3 → [10, 13, 14, 29, 37]
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Terminology:

The outer loop’s i marks the edge of the sorted section. The last element needs no pass of its own, because once everything else is placed it is already in the right spot.

B. Insertion Sort. The InsertionTrace class prints the array after every insertion

Code Runner Challenge

Replace the sample values with your own, then run it

View IPYNB Source
// CODE_RUNNER: Predict every insertion on paper first, then run it and compare
import java.util.Arrays;

public class InsertionTrace {
    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;
            System.out.println("Insert index " + i + " (" + key + "): " + Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        int[] tickets = {29, 10, 14, 37, 13};
        System.out.println("Start: " + Arrays.toString(tickets));
        insertionSort(tickets);
    }
}

InsertionTrace.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...
Click to reveal the trace

Code Runner Challenge

Fill in the blanks, then run it

View IPYNB Source
Start:                [29, 10, 14, 37, 13]
Insert index 1 (10):  shift 29 → [10, 29, 14, 37, 13]
Insert index 2 (14):  shift 29, stop at 10 → [10, 14, 29, 37, 13]
Insert index 3 (37):  no shifts → [10, 14, 29, 37, 13]
Insert index 4 (13):  shift 37, 29, 14, stop at 10 → [10, 13, 14, 29, 37]
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Common insertion mistake:

while (arr[j] > key)               // missing j >= 0: crashes when key is the smallest
while (j >= 0 && arr[j] > key)     // correct: stop at the front of the line

Terminology:

The outer loop starts at 1 because one car by itself is already a sorted line. key is the car pulling up, and the while loop is the valet walking backward.

C. Comparing the work. The ComparisonCounter class counts comparisons on sorted and reversed input

// CODE_RUNNER: Run it, then try a nearly sorted array like {1, 2, 4, 3, 5} and explain the counts
public class ComparisonCounter {
    public static int selectionComparisons(int[] arr) {
        int count = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                count++;
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return count;
    }

    public static int insertionComparisons(int[] arr) {
        int count = 0;
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0) {
                count++;
                if (arr[j] > key) {
                    arr[j + 1] = arr[j];
                    j--;
                } else {
                    break;
                }
            }
            arr[j + 1] = key;
        }
        return count;
    }

    public static void main(String[] args) {
        int[] sorted = {1, 2, 3, 4, 5};
        int[] reversed = {5, 4, 3, 2, 1};

        System.out.println("Sorted input   - Selection: " + selectionComparisons(sorted.clone())
                + ", Insertion: " + insertionComparisons(sorted.clone()));
        System.out.println("Reversed input - Selection: " + selectionComparisons(reversed.clone())
                + ", Insertion: " + insertionComparisons(reversed.clone()));
    }
}

ComparisonCounter.main(null);

Terminology:

Selection Sort always makes the same number of comparisons for a given length. Insertion Sort stops early when the next car is already bigger than the one before it, so already sorted input costs only one comparison per element.

Hacks & Practice Tasks

Popcorn Hack

2-minute challenge: trace both sorts on your own array.

  • Pick 5 different ticket numbers in a scrambled order
  • In a markdown cell, write the array after every pass of Selection Sort
  • Write the array after every insertion of Insertion Sort
  • Run the cell and check your predictions against the output
  • Circle the first pass (if any) where your prediction was wrong

Replace the sample values with your own.

// CODE_RUNNER: Replace the sample values with your own, then run it
import java.util.Arrays;

public class TraceBoth {
    public static void main(String[] args) {
        // Try writing your own predictions first!

        // Sample answer:
        int[] original = {42, 8, 15, 4, 23};

        int[] sel = original.clone();
        System.out.println("Selection start: " + Arrays.toString(sel));
        for (int i = 0; i < sel.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < sel.length; j++) {
                if (sel[j] < sel[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = sel[i];
            sel[i] = sel[minIndex];
            sel[minIndex] = temp;
            System.out.println("Pass " + (i + 1) + ": " + Arrays.toString(sel));
        }

        int[] ins = original.clone();
        System.out.println("Insertion start: " + Arrays.toString(ins));
        for (int i = 1; i < ins.length; i++) {
            int key = ins[i];
            int j = i - 1;
            while (j >= 0 && ins[j] > key) {
                ins[j + 1] = ins[j];
                j--;
            }
            ins[j + 1] = key;
            System.out.println("Insert " + key + ": " + Arrays.toString(ins));
        }
    }
}

TraceBoth.main(null);
Click to reveal the sample traces
Selection:
Pass 1: smallest is 4 → swap with index 0     → [4, 8, 15, 42, 23]
Pass 2: 8 already in place                    → [4, 8, 15, 42, 23]
Pass 3: 15 already in place                   → [4, 8, 15, 42, 23]
Pass 4: smallest in [42,23] is 23 → swap      → [4, 8, 15, 23, 42]

Insertion:
Insert 8:  shift 42                           → [8, 42, 15, 4, 23]
Insert 15: shift 42, stop at 8                → [8, 15, 42, 4, 23]
Insert 4:  shift 42, 15, 8                    → [4, 8, 15, 42, 23]
Insert 23: shift 42, stop at 15               → [4, 8, 15, 23, 42]

MCQ Check

6 questions, one at a time. Answer, check, then go to the next one. At the end, copy the score line into your notes.

MCQ Check
6 questions. Pick an answer to see feedback.
Question 1

Selection Sort runs on {29, 10, 14, 37, 13}. What does the array look like after the first pass?

Question 2

Insertion Sort runs on {29, 10, 14, 37, 13}. What does the array look like after the insertion at i = 2?

Question 3

What is the most swaps Selection Sort makes in one pass?

Question 4

The array {5, 3, 8, 4, 9} is being sorted. After the second pass it looks like [3, 5, 8, 4, 9]. Which algorithm is running?

Question 5

The array is already sorted. Which algorithm makes fewer comparisons?

Question 6

What happens if j >= 0 is removed from Insertion Sort's while condition?

Homework Hack

Task: Sort the garage both ways. Store the garage name in a final variable and five ticket numbers in an int array. Sort one copy with Selection Sort and count the swaps (only count when minIndex != i). Sort another copy with Insertion Sort and count the shifts. Print the array after every pass for both. Then run both on an already sorted array and explain in a markdown cell which one did less work and why.

Solution Skeleton:

// CODE_RUNNER: Fill in the blanks, then run it
import java.util.Arrays;

public class SortTheGarage {
    // 1. Selection Sort: print each pass, return the number of swaps
    public static int selectionSort(int[] arr) {
        int swaps = 0;
        return swaps;
    }

    // 2. Insertion Sort: print each insertion, return the number of shifts
    public static int insertionSort(int[] arr) {
        int shifts = 0;
        return shifts;
    }

    public static void main(String[] args) {
        final String GARAGE_NAME = "Your Garage Name";
        int[] tickets = {0, 0, 0, 0, 0};

        int[] selCopy = tickets.clone();
        int swaps = selectionSort(selCopy);
        System.out.println(GARAGE_NAME + " selection: " + Arrays.toString(selCopy) + ", swaps: " + swaps);

        int[] insCopy = tickets.clone();
        int shifts = insertionSort(insCopy);
        System.out.println(GARAGE_NAME + " insertion: " + Arrays.toString(insCopy) + ", shifts: " + shifts);

        // 3. Run both sorts on an already sorted array and print the counts
    }
}

SortTheGarage.main(null);

References

College Board. (2025). AP Computer Science A course and exam description [Effective fall 2025].

Hoffman, B., et al. (2025). 4.15 Sorting algorithms. In CSAwesome2: AP CSA Java 2026+. Runestone Academy.

Halim, S. (n.d.). Sorting. VisuAlgo.

All Java lessons