4.15 Sorting Algorithms
Trace and implement sorting algorithms that arrange array values into ascending or descending order.
- Reference Guide
- College Board Requirements
- Lesson Plan
- Tech Talk
- Code Runner Challenge
- Code Examples
- A. Selection Sort. The
SelectionTraceclass prints the array after every pass - Code Runner Challenge
- Code Runner Challenge
- Code Runner Challenge
- B. Insertion Sort. The
InsertionTraceclass prints the array after every insertion - Code Runner Challenge
- Code Runner Challenge
- C. Comparing the work. The
ComparisonCounterclass counts comparisons on sorted and reversed input
- A. Selection Sort. The
- Hacks & Practice Tasks
- References
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
iis 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 firstkspots hold theksmallest values in the whole array → Selection Sort - After pass
k, the firstk + 1spots 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.
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 + ")");
}
}
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);
Code Examples
A. Selection Sort. The SelectionTrace class prints the array after every pass
Three parts of each pass get mixed up a lot:
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);
}
}
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
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);
}
}
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);
Click to reveal the trace
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()));
}
}
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]
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
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));
}
}
}
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);
Click to reveal the trace
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
}
}
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]
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.
Selection Sort runs on {29, 10, 14, 37, 13}. What does the array look like after the first pass?
Insertion Sort runs on {29, 10, 14, 37, 13}. What does the array look like after the insertion at i = 2?
What is the most swaps Selection Sort makes in one pass?
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?
The array is already sorted. Which algorithm makes fewer comparisons?
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].