Sorting Algorithms in AP CSA: Complete Guide (2025-2026)

AP CSA tests two sorting algorithms: selection sort and insertion sort. Both are O(n²) and sort in place. You need to trace them step by step, spot broken swap code, and calculate comparison counts. This is Unit 4 content (Data Collections, 30–40% of the exam).

Selection Sort

• Outer loop: i from 0 to arr.length − 2
• Inner loop: j from i+1 to arr.length − 1 — finds minimum index in unsorted portion
• Swap arr[i] with arr[minIdx]
• After pass i, arr[0..i] is in final position
• Always makes exactly n(n−1)/2 comparisons

Insertion Sort

• Outer loop: i from 1 to arr.length − 1
• Save key = arr[i]; shift elements greater than key rightward
• Place key in the gap
• After pass i, arr[0..i] is sorted
• Efficient on nearly-sorted data

Code Examples

Example 1: Selection Sort

public class SelectSort {
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < arr.length; j++)
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            int tmp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = tmp;
        }
    }
    public static void main(String[] args) {
        int[] data = {64, 25, 12, 22};
        selectionSort(data);
        for (int v : data) System.out.print(v + " ");
    }
}

Example 2: Insertion Sort

public class InsertSort {
    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;
        }
    }
    public static void main(String[] args) {
        int[] data = {5, 3, 8, 1, 4};
        insertionSort(data);
        for (int v : data) System.out.print(v + " ");
    }
}

Example 3: Tracing Pass-by-Pass

public class SortTrace {
    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 2};
        for (int i = 0; i < arr.length - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < arr.length; j++)
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            int tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp;
            System.out.print("Pass " + (i+1) + ": ");
            for (int v : arr) System.out.print(v + " ");
            System.out.println();
        }
    }
}

Common Pitfalls

Check for Understanding

int minIdx = i;
for (int j = i+1; j < arr.length; j++)
    if (arr[j] < arr[minIdx]) {
        minIdx = j;
    }
int tmp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = arr[i];   // ← line X

int tmp = arr[i];
arr[i] = arr[minIdx];
________ = tmp;

Frequently Asked Questions

Related Topics