---
title: "AP Computer Science A 4.15: Sorting Algorithms"
description: "Review AP CSA sorting algorithms, including selection sort, insertion sort, tracing arrays and ArrayLists, swaps, shifts, and comparisons."
canonical: "https://fiveable.me/ap-comp-sci-a/unit-4/sorting/study-guide/P5PACxSTKavEy6V3x3Nt"
type: "study-guide"
subject: "AP Computer Science A"
unit: "Unit 4 – Data Collections"
lastUpdated: "2026-06-07"
---

# AP Computer Science A 4.15: Sorting Algorithms

## Summary

Review AP CSA sorting algorithms, including selection sort, insertion sort, tracing arrays and ArrayLists, swaps, shifts, and comparisons.

## Guide

## TLDR
Selection sort and insertion sort are the two iterative sorting algorithms you need to trace for [AP Computer Science A](/ap-comp-sci-a "fv-autolink"). 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](/ap-comp-sci-a/unit-4/array-creation-and-access/study-guide/umTe6NA38OqZOhMZjFWi "fv-autolink") or ArrayList after each pass.

## 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](/ap-comp-sci-a/key-terms/algorithm "fv-autolink") 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](/ap-comp-sci-a/key-terms/index "fv-autolink") bounds.

This topic builds directly on array and ArrayList [traversal](/ap-comp-sci-a/key-terms/traversal "fv-autolink") skills, so being able to walk through [nested loops](/ap-comp-sci-a/key-terms/nested-loops "fv-autolink") 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](/ap-comp-sci-a/key-terms/tracing "fv-autolink") 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](/ap-comp-sci-a/key-terms/object "fv-autolink"), you compare based on a chosen [attribute](/ap-comp-sci-a/key-terms/attribute "fv-autolink") (like a student's GPA).

### Selection Sort

Selection sort splits the [list](/ap-comp-sci-a/key-terms/list "fv-autolink") 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](/ap-comp-sci-a/key-terms/outer-loop "fv-autolink") tracks which position you are filling. The [inner loop](/ap-comp-sci-a/key-terms/inner-loop "fv-autolink") 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](/ap-comp-sci-a/unit-1/14-assignment-statement-input/study-guide/compoundassignment "fv-autolink"), 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](/ap-comp-sci-a/unit-1/expressions-and-assignment-statements/study-guide/01dr6uUPDAn3SjtK2Psr "fv-autolink") 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](/ap-comp-sci-a/key-terms/loop "fv-autolink") 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](/ap-comp-sci-a/key-terms/merge-sort "fv-autolink") 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](/ap-comp-sci-a/unit-4/2d-arrays/study-guide/5WDx6ZFeWhx2aVuiZI6R)
- [4.5 Developing Algorithms Using Arrays](/ap-comp-sci-a/unit-4/developing-algorithms-using-arrays/study-guide/c6dpJfmjG7oVFDqnXFAk)
- [4.1 Ethical and Social Implications](/ap-comp-sci-a/unit-4/ethical-and-social-implications/study-guide/iec7yzDQ2qENx5UAdiPJ)
- [4.9 Traversing ArrayLists](/ap-comp-sci-a/unit-4/traversing-arraylists/study-guide/U4SdcheNw5PMSIzjU2oL)
- [4.13 Implementing 2D Array Algorithms](/ap-comp-sci-a/unit-4/implementing-2d-array-algorithms/study-guide/9ucC5cB6ffrLnA4b3FU3)
- [4.16 Recursion](/ap-comp-sci-a/unit-4/recursion/study-guide/p4D3YegZCLwQ3KJVvsd4)

## Vocabulary

- **ArrayList**: A resizable array implementation in Java that can dynamically grow or shrink to store a collection of objects.
- **array**: A data structure that stores a fixed-size collection of elements of the same type in contiguous memory locations, accessed by index.
- **insertion sort**: An iterative sorting algorithm that inserts elements from the unsorted portion into their correct position in the sorted portion by shifting elements to make room.
- **iterative sorting algorithms**: Sorting algorithms that use repetition to progressively sort elements by performing the same operation multiple times.
- **selection sort**: An iterative sorting algorithm that repeatedly selects the smallest or largest element from the unsorted portion and places it in its correct final position in the sorted portion.
- **sorted portion**: The part of a collection that has been arranged in the desired order during a sorting process.
- **sorting algorithms**: Step-by-step procedures used to arrange elements in a collection in a specific order, such as ascending or descending.
- **swap**: The operation of exchanging the positions of two elements in a collection.
- **unsorted portion**: The part of a collection that has not yet been arranged in the desired order during a sorting process.

## FAQs

### What sorting algorithms are tested in AP Computer Science A?

AP CSA expects you to trace selection sort and insertion sort on arrays or ArrayLists. You should understand each algorithm step by step rather than memorize only final sorted output.

### How does selection sort work?

Selection sort repeatedly finds the smallest or largest value in the unsorted portion of the list and swaps it into its correct final position in the sorted portion.

### How does insertion sort work?

Insertion sort takes the next item from the unsorted portion and inserts it into the correct position in the sorted portion by shifting elements to make room.

### What is the biggest difference between selection sort and insertion sort?

Selection sort places one value into its final position each pass. Insertion sort builds a sorted portion whose values are ordered but not necessarily in their final positions until more items are inserted.

### How do sorting questions show up on AP CSA?

Sorting questions often ask you to trace array values after one pass, count comparisons or swaps, or determine the result of executing code that implements selection sort or insertion sort.

### What should I watch for when tracing sorting code?

Track loop bounds, index variables, and whether the code swaps values or shifts values. Off-by-one errors are the most common reason students choose the wrong intermediate array state.

## Structured Data

```json
{"@context":"https://schema.org","@type":"FAQPage","inLanguage":"en","mainEntity":[{"@type":"Question","@id":"https://fiveable.me/ap-comp-sci-a/unit-4/sorting/study-guide/P5PACxSTKavEy6V3x3Nt#what-sorting-algorithms-are-tested-in-ap-computer-science-a","name":"What sorting algorithms are tested in AP Computer Science A?","acceptedAnswer":{"@type":"Answer","text":"AP CSA expects you to trace selection sort and insertion sort on arrays or ArrayLists. You should understand each algorithm step by step rather than memorize only final sorted output."}},{"@type":"Question","@id":"https://fiveable.me/ap-comp-sci-a/unit-4/sorting/study-guide/P5PACxSTKavEy6V3x3Nt#how-does-selection-sort-work","name":"How does selection sort work?","acceptedAnswer":{"@type":"Answer","text":"Selection sort repeatedly finds the smallest or largest value in the unsorted portion of the list and swaps it into its correct final position in the sorted portion."}},{"@type":"Question","@id":"https://fiveable.me/ap-comp-sci-a/unit-4/sorting/study-guide/P5PACxSTKavEy6V3x3Nt#how-does-insertion-sort-work","name":"How does insertion sort work?","acceptedAnswer":{"@type":"Answer","text":"Insertion sort takes the next item from the unsorted portion and inserts it into the correct position in the sorted portion by shifting elements to make room."}},{"@type":"Question","@id":"https://fiveable.me/ap-comp-sci-a/unit-4/sorting/study-guide/P5PACxSTKavEy6V3x3Nt#what-is-the-biggest-difference-between-selection-sort-and-insertion-sort","name":"What is the biggest difference between selection sort and insertion sort?","acceptedAnswer":{"@type":"Answer","text":"Selection sort places one value into its final position each pass. Insertion sort builds a sorted portion whose values are ordered but not necessarily in their final positions until more items are inserted."}},{"@type":"Question","@id":"https://fiveable.me/ap-comp-sci-a/unit-4/sorting/study-guide/P5PACxSTKavEy6V3x3Nt#how-do-sorting-questions-show-up-on-ap-csa","name":"How do sorting questions show up on AP CSA?","acceptedAnswer":{"@type":"Answer","text":"Sorting questions often ask you to trace array values after one pass, count comparisons or swaps, or determine the result of executing code that implements selection sort or insertion sort."}},{"@type":"Question","@id":"https://fiveable.me/ap-comp-sci-a/unit-4/sorting/study-guide/P5PACxSTKavEy6V3x3Nt#what-should-i-watch-for-when-tracing-sorting-code","name":"What should I watch for when tracing sorting code?","acceptedAnswer":{"@type":"Answer","text":"Track loop bounds, index variables, and whether the code swaps values or shifts values. Off-by-one errors are the most common reason students choose the wrong intermediate array state."}}]}
```