4.15 Sorting

TLDR

Selection sort and insertion sort are the two iterative sorting algorithms you need to trace for AP Computer Science A. Selection sort repeatedly grabs the smallest (or largest) value from the unsorted part and swaps it into its final spot, while insertion sort takes each new value and slides it into the correct place inside the already-sorted part. For this topic, your main job is to follow each step and predict the array or ArrayList after each pass.

more resources to help you study

practice multiple choiceFRQ practice & scoringcheatsheetsscore calculator

Why This Matters for the AP Computer Science A Exam

Sorting shows up most often as code-tracing work. You will be asked to determine the result of executing each step of a sorting algorithm and to describe how an array or ArrayList changes after one pass or several passes. You also need to recognize the conditions a sort assumes, like comparing elements correctly and staying inside valid index bounds.

This topic builds directly on array and ArrayList traversal skills, so being able to walk through nested loops carefully is what earns points. The exam expects you to read and trace selection sort and insertion sort rather than memorize a single canned implementation.

Key Takeaways

• Selection sort and insertion sort are both iterative and both work on arrays or ArrayLists.
• Selection sort finds the smallest (or largest) element in the unsorted portion and swaps it into its final position each pass.
• Insertion sort takes the next unsorted element and shifts larger sorted elements right to open a spot for it.
• In selection sort, once an element is placed, it does not move again; in insertion sort, an inserted element can still shift later.
• Insertion sort runs fast on data that is already nearly sorted, while selection sort does the same amount of work no matter the order.
• Tracing carefully, pass by pass, is how you answer sorting questions correctly.

Key Concepts

What Sorting Means

Sorting rearranges elements in a collection so they follow a specific order, usually ascending or descending based on some comparison. To sort, you need a clear way to compare two elements.

</>Java
// Unsorted array
int[] numbers = {64, 34, 25, 12, 22, 11, 90};

// After sorting (ascending)
// [11, 12, 22, 25, 34, 64, 90]

For numbers, you compare with the usual less-than and greater-than. For objects, you compare based on a chosen attribute (like a student's GPA).

Selection Sort

Selection sort splits the list into a sorted portion (front) and an unsorted portion (rest). Each pass scans the unsorted portion, finds the smallest element, and swaps it into the next sorted position. Once placed, that element is in its final spot and never moves again.

</>Java
public static void selectionSort(int[] arr) {
    int n = arr.length;

    // Outer loop: position to fill (building from left to right)
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;  // Assume current position has minimum

        // Inner loop: find the actual minimum in remaining elements
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;  // Found a smaller element
            }
        }

        // Place the minimum element in its correct position
        if (minIndex != i) {
            swap(arr, i, minIndex);
        }
    }
}

// Helper method for clean code organization
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

The outer loop tracks which position you are filling. The inner loop finds the minimum in the remaining elements. To sort in descending order, look for the largest element instead of the smallest.

Insertion Sort

Insertion sort also keeps a sorted portion at the front, but it builds it differently. It takes the next unsorted element (the key), then shifts each larger element in the sorted portion one spot to the right to make room, and finally drops the key into the opening.

</>Java
public static void insertionSort(int[] arr) {
    int n = arr.length;

    // Start from second element (first element is trivially sorted)
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // Element to be inserted
        int j = i - 1;     // Start checking from sorted portion

        // Shift larger elements one position right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];  // Make room for the key
            j--;
        }

        // Insert the key in its correct position
        arr[j + 1] = key;
    }
}

Think of sorting cards in your hand: you pick up the next card and slide it left until it sits in the right spot. A position that looks correct early on can still shift as later elements get inserted, which is the opposite of selection sort.

How the Two Sorts Compare

Both selection sort and insertion sort do roughly the same amount of work on a worst-case input, but their step-by-step behavior differs.

Selection sort

• Scans the same number of elements every pass, no matter the input order.
• Makes at most one swap per pass.
• Does the same amount of comparison work whether the data is sorted or scrambled.

Insertion sort

• On nearly sorted data, it barely shifts anything and finishes quickly.
• On reverse-sorted data, it shifts a lot and does its maximum work.
• Behavior depends heavily on how ordered the input already is.

The big tracing difference: in selection sort, a placed element is final, while in insertion sort, an already-placed element can still slide when a new key is inserted.

Sorting Objects

When you sort objects, you decide the comparison rule by reading an attribute. Here insertion sort orders students by GPA from highest to lowest.

</>Java
public class Student {
    private String name;
    private double gpa;
    private int graduationYear;

    public Student(String name, double gpa, int year) {
        this.name = name;
        this.gpa = gpa;
        this.graduationYear = year;
    }

    // Accessors needed for comparison
    public double getGPA() { return gpa; }
    public String getName() { return name; }
    public int getGraduationYear() { return graduationYear; }
}

// Sorting students by GPA using insertion sort
public static void sortStudentsByGPA(Student[] students) {
    for (int i = 1; i < students.length; i++) {
        Student key = students[i];
        int j = i - 1;

        // Compare GPAs (descending order - highest first)
        while (j >= 0 && students[j].getGPA() < key.getGPA()) {
            students[j + 1] = students[j];
            j--;
        }
        students[j + 1] = key;
    }
}

The algorithm structure stays the same; only the comparison changes from comparing numbers to comparing an attribute.

Code Examples

Tracing Selection Sort

This version prints the array after each placement so you can follow the passes.

</>Java
public class SelectionSortDemo {
    public static void selectionSort(int[] arr) {
        System.out.println("Starting Selection Sort:");
        printArray("Initial", arr);

        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;

            // Find minimum element in remaining unsorted portion
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // Swap minimum element to current position
            if (minIndex != i) {
                swap(arr, i, minIndex);
                System.out.printf("Step %d: Placed %d in position %d%n",
                                i + 1, arr[i], i);
                printArray("Current", arr);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void printArray(String label, int[] arr) {
        System.out.print(label + ": ");
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] data = {64, 34, 25, 12, 22, 11, 90};
        selectionSort(data);
    }
}

Tracing Insertion Sort

</>Java
public class InsertionSortDemo {
    public static void insertionSort(int[] arr) {
        System.out.println("Starting Insertion Sort:");
        printArray("Initial", arr);

        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;

            System.out.printf("Inserting %d into sorted portion%n", key);

            // Shift elements larger than key one position right
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            // Insert key in correct position
            arr[j + 1] = key;

            System.out.printf("Step %d: ", i);
            printArray("Current", arr);
        }
    }

    private static void printArray(String label, int[] arr) {
        System.out.print(label + ": ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Counting Comparisons and Swaps

Counting operations is a good way to see why the two sorts behave differently on the same data.

</>Java
public class SortingComparison {
    private static long comparisons = 0;
    private static long swaps = 0;

    public static void selectionSortWithCounting(int[] arr) {
        comparisons = 0;
        swaps = 0;

        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;

            for (int j = i + 1; j < arr.length; j++) {
                comparisons++;  // Count each comparison
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            if (minIndex != i) {
                swap(arr, i, minIndex);
                swaps++;  // Count each swap
            }
        }

        System.out.println("Selection Sort - Comparisons: " + comparisons +
                          ", Swaps: " + swaps);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

How to Use This on the AP Computer Science A Exam

Code Tracing

Most sorting questions ask you to predict the array after a specific number of passes. Use a small sample array and write out its state after each outer-loop pass.

• For selection sort, after pass number k, the first k positions hold the smallest k values in final order.
• For insertion sort, after processing index i, elements from index 0 to i are sorted among themselves but may still shift later.
• Track index variables like i, j, minIndex, and key in a side column so you do not lose your place.

Describing Behavior

Some questions ask you to describe what a pass does or what the algorithm guarantees. Be precise: selection sort places one element in its final position per pass, while insertion sort grows a sorted prefix that can still rearrange.

Checking Conditions

Sorting code only works when the loop bounds and comparisons are correct. When a question asks why a sort fails or what must be true, check that the inner loop stays inside valid indices and that the comparison matches the intended order (ascending versus descending).

Common Trap

The while loop in insertion sort needs both j >= 0 and arr[j] > key. If you trace only the comparison and forget the index check, you will read a negative index that does not exist. Always evaluate the boundary condition first.

Common Misconceptions

• Selection sort and insertion sort are the iterative sorts in this topic. Merge sort is recursive and belongs to a later topic, so do not mix it in here.
• A placed selection-sort element is final, but an inserted insertion-sort element is not guaranteed final; it can still slide right as later keys are inserted.
• Both sorts can run in descending order. Sorting is not locked to ascending; the comparison direction decides the order.
• Insertion sort being faster on nearly sorted data does not change its worst case. On reverse-sorted input it still does the maximum amount of work.
• The inner while condition order matters. You must check j >= 0 before arr[j] > key, or you risk accessing an invalid index.
• Sorting works on both arrays and ArrayLists. With an ArrayList you use get and set instead of square-bracket indexing, but the logic is the same.

Related AP Computer Science A Guides

• 4.11 2D Arrays
• 4.5 Developing Algorithms Using Arrays
• 4.1 Ethical and Social Implications
• 4.9 Traversing ArrayLists
• 4.13 Implementing 2D Array Algorithms
• 4.16 Recursion