1. 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)

2. LxD Cycle Process

Empathize: Students can recite both algorithms but mix up swapping and shifting halfway through a trace, count a swap every time Selection Sort finds a smaller value, and struggle when handed a half-sorted array and asked which algorithm produced it. The exam asks exactly that kind of question.

Define:

• POV: CSA students need to see each sort as a physical strategy (a sweep vs. a valet line), because the strategy tells them what the array must look like after each pass.
• Learning Goal: Students will trace Selection Sort and Insertion Sort pass by pass, identify which algorithm produced a partially sorted array, and compare how much work each one does.

Ideate:

• HMW Question: How might we get students to predict the array after each pass before they run the code?
• HMW Question: How might we make the difference between one swap and many shifts visible?
• Activity: Trace both sorts on your own array in the popcorn hack, identify algorithms from partial traces in the MCQ, then count swaps and shifts in the homework.

Prototype:

• A reference guide, runnable Java examples that print every pass, a popcorn hack, an MCQ knowledge check, and a scaffolded grade rubric.
• Students compare their hand traces to runner output and fix the first pass where they went wrong.
• Excellence means explaining why each pass looks the way it does, counting moves correctly, and improving the first attempt rather than only producing working code.

Test:

• Ask peers in peer review to complete the practice without additional explanation.
• Observe whether peers can name the algorithm from one partial trace.
• Compare your lesson with another that is posted.
• Use the findings to revise any instruction or rubric criterion that did not guide students clearly.
• On submission, collect evidence from runner output, MCQ results, AI grading and student explanations.
• After teaching, grading and analysis, come back and revise lesson to complete teaching cycle for continuous improvement.

3. 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.

4. 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 (5 minutes)

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);

Python Java JavaScript Pseudocode 14px 16px 18px 20px

Lines: 1 Characters: 0

Output

Click "Run" in code control panel to see output ...

5. 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

Python Java JavaScript Pseudocode 14px 16px 18px 20px

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);

Python Java JavaScript Pseudocode 14px 16px 18px 20px

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]

Python Java JavaScript Pseudocode 14px 16px 18px 20px

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);

Python Java JavaScript Pseudocode 14px 16px 18px 20px

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]

Python Java JavaScript Pseudocode 14px 16px 18px 20px

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.

6. Hacks & Practice Tasks

Prepare your submission IPYNB

1. Create a new notebook in your portfolio homework area: _notebooks/homework.
2. Add one raw cell at the top with the frontmatter (same fields as your other homework notebooks).
3. Add code cells for the Popcorn Hack and the Homework Hack. Make sure every cell runs with visible output.
4. Submit the link to your published page at the bottom of this page, and paste this in the description box:

Lesson: CSA 4.15 Sorting Algorithms
MCQ 4.15: <paste your result line, such as 5/6 | answers: A,B,B,B,B,C>
Popcorn: own 5-value array, hand predictions written for both sorts, runner output matches (yes/no)
Homework: final garage name used (yes/no)
Homework: starting tickets = <values>
Homework: selection sorted = <values>, swaps = <count>
Homework: insertion sorted = <values>, shifts = <count>
Homework: on already sorted input, fewer moves by = <Selection/Insertion>, because <one sentence>

Submission Safety Rules (Read First)

• One class per cell, ending with ClassName.main(null);.
• Run each cell and leave the output showing.
• Use your own values, not the sample answer.
• Include your MCQ score.
• Use ## headings or smaller.

Popcorn Hack (In-Class)

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 submission notes.

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);

Grading Plan (1 Point Total)

Part	Points	What earns the points
Popcorn	0.2	Own 5-value array, written predictions for both sorts, and the cell runs.
MCQ	0.2	5 or 6 correct. 0.15 for 3 or 4, 0.1 if every question was answered.
Homework: selection	0.15	Selection Sort sorts correctly and counts swaps.
Homework: insertion	0.15	Insertion Sort sorts correctly and counts shifts.
Homework: passes	0.15	Array printed after every pass of both sorts.
Homework: comparison	0.15	Both sorts run on sorted input, counts printed, and a correct explanation written.
Total	1.0

Quick Validation Checklist

• Each cell ends with ClassName.main(null); and shows output.
• MCQ score in the notes.
• final on the garage name.
• Each sort works on its own copy of the array.
• Insertion Sort’s while checks j >= 0 first.
• Sorted-input comparison printed and explained.

7. Lesson Revisions

Revision Made: Lesson authors: what you changed because of it.

8. Feedback Evidence

Feedback Received: Lesson authors: what your peers said in the practice run.

---

9. 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.