Sorting

Sorting is the process of arranging an array's elements in order, typically smallest to largest. AP CSA focuses on two specific algorithms: selection sort and insertion sort.

Both run in-place (no extra array needed) and use nested loops. They differ in how they build the sorted region: selection sort finds the minimum each pass; insertion sort places each new element into its correct position.

On the AP exam, sorting appears in MCQ tracing problems ("what does the array look like after pass 3?"), in conceptual questions, and in occasional FRQ subparts that require implementing or modifying a sort.

Selection sort

Idea. On each pass, find the smallest remaining element and swap it into the next sorted position.

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;
            }
        }
        // swap arr[i] and arr[minIndex]
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

After pass i, the first i + 1 elements are in their final sorted positions.

Insertion sort

Idea. Treat the array's left side as already sorted. Take each new element and shift it left until it's in the right place.

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int current = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j];   // shift right
            j--;
        }
        arr[j + 1] = current;      // place into the gap
    }
}

After processing index i, the subarray arr[0..i] is sorted relative to itself.

Trace patterns

For both algorithms, the AP exam often asks for the array state after a specific pass. Trace each pass on paper and write the resulting array.

Performance

Both selection and insertion sort make on the order of n² comparisons in the worst case. Insertion sort can be much faster on nearly-sorted data because the inner loop exits quickly.