# AP® Computer Science A 4.15 Sorting Algorithms

Source: https://lockincs.com/ap-csa/unit-4/4-15-sorting-algorithms/  
Last reviewed against the College Board Course and Exam Description (CED): 2026-11-12  
CED codes: 4.15.A, 4.15.A.1, 4.15.A.2, 4.15.A.3

Selection sort and insertion sort are iterative sorting algorithms for an array or ArrayList. Selection sort repeatedly selects the smallest (or largest) element of the unsorted portion and swaps it into its final position. Insertion sort takes the next element of the unsorted portion and shifts larger elements of the sorted portion to insert it in its correct, but not necessarily final, position.

## What you will learn

- 4.15.A Determine the result of executing each step of sorting algorithms to sort the elements of a collection.

## 1\. Two iterative sorts

Selection sort and insertion sort are **iterative** sorting algorithms: they use loops (not recursion) and can sort the elements of an array or an ArrayList 4.15.A.1. Both split the list into a **sorted portion** at the front and an **unsorted portion** after it. Each pass of the outer loop makes the sorted portion one element longer, so a list of n elements needs n - 1 passes.

Every example on this page sorts the same six race times (in seconds) into increasing order:

| index | 0 | 1 | 2 | 3 | 4 | 5 |
| --- | --- | --- | --- | --- | --- | --- |
| value | 29 | 12 | 41 | 7 | 18 | 33 |

## 2\. Selection sort

Selection sort repeatedly selects the smallest element from the unsorted portion and swaps it into its correct and final position at the end of the sorted portion 4.15.A.2. (A version that selects the largest element and swaps it to the back works the same way.)

```
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));
    }
}

int[] times = {29, 12, 41, 7, 18, 33};
selectionSort(times);
```

Output:

```
pass 1: [7, 12, 41, 29, 18, 33]
pass 2: [7, 12, 41, 29, 18, 33]
pass 3: [7, 12, 18, 29, 41, 33]
pass 4: [7, 12, 18, 29, 41, 33]
pass 5: [7, 12, 18, 29, 33, 41]
```

(`Arrays.toString` is only used here to show the array; it is not part of the AP® Java Quick Reference.)

Pass by pass (bold = sorted portion, which is final):

| Pass | Minimum found | Swap | Array after the pass | Comparisons |
| --- | --- | --- | --- | --- |
| start |  |  | 29 12 41 7 18 33 |  |
| 1 | 7 (index 3) | index 0 and 3 | **7** 12 41 29 18 33 | 5 |
| 2 | 12 (index 1) | with itself | **7 12** 41 29 18 33 | 4 |
| 3 | 18 (index 4) | index 2 and 4 | **7 12 18** 29 41 33 | 3 |
| 4 | 29 (index 3) | with itself | **7 12 18 29** 41 33 | 2 |
| 5 | 33 (index 5) | index 4 and 5 | **7 12 18 29 33** 41 | 1 |

Total: 5 + 4 + 3 + 2 + 1 = 15 comparisons. For n elements selection sort always makes n(n - 1) / 2 comparisons, even when the list starts sorted, because it must check every unsorted element to be sure it has the minimum.

Watch out: on passes 2 and 4 the minimum was already in place, so the array did not change. A question asking for “the array after pass 2” expects the same array as after pass 1.

## 3\. Insertion sort

Insertion sort takes the first element of the unsorted portion and inserts it into its correct, but not necessarily final, position in the sorted portion. It makes room by shifting the larger elements of the sorted portion one place to the right 4.15.A.3.

```
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];   // shift right
            j--;
        }
        arr[j + 1] = key;          // insert into the gap
        System.out.println("pass " + i + ": " + Arrays.toString(arr));
    }
}

int[] times = {29, 12, 41, 7, 18, 33};
insertionSort(times);
```

Output:

```
pass 1: [12, 29, 41, 7, 18, 33]
pass 2: [12, 29, 41, 7, 18, 33]
pass 3: [7, 12, 29, 41, 18, 33]
pass 4: [7, 12, 18, 29, 41, 33]
pass 5: [7, 12, 18, 29, 33, 41]
```

Pass by pass (bold = sorted portion, which is sorted but not final):

| Pass | Element inserted (key) | Elements shifted right | Array after the pass | Comparisons (arr\[j\] > key) |
| --- | --- | --- | --- | --- |
| start |  |  | **29** 12 41 7 18 33 |  |
| 1 | 12 | 29 | **12 29** 41 7 18 33 | 1 |
| 2 | 41 | none | **12 29 41** 7 18 33 | 1 |
| 3 | 7 | 41, 29, 12 | **7 12 29 41** 18 33 | 3 |
| 4 | 18 | 41, 29 | **7 12 18 29 41** 33 | 3 |
| 5 | 33 | 41 | **7 12 18 29 33 41** | 2 |

Total: 1 + 1 + 3 + 3 + 2 = 10 comparisons. In pass 1, 12 and 29 are in order with each other, but neither is final: on pass 3, the value 7 pushes both of them right.

Watch out: on pass 3 the loop stops because `j` becomes -1, not because of a comparison. The `&&` short-circuits, so `arr[-1]` is never read.

## 4\. Sorting an ArrayList

Both algorithms work on an ArrayList too 4.15.A.1. Replace `arr[i]` with `get(i)`, assignments with `set(i, value)` and `length` with `size()`.

```
ArrayList<String> names = new ArrayList<String>();
names.add("Mia");
names.add("Ali");
names.add("Zoe");
names.add("Ben");

// selection sort, alphabetical order
for (int i = 0; i < names.size() - 1; i++)
{
    int minIndex = i;
    for (int j = i + 1; j < names.size(); j++)
    {
        if (names.get(j).compareTo(names.get(minIndex)) < 0)
        {
            minIndex = j;
        }
    }
    String temp = names.get(i);
    names.set(i, names.get(minIndex));
    names.set(minIndex, temp);
}
System.out.println(names);
```

Output:

```
[Ali, Ben, Mia, Zoe]
```

## 5\. Comparing the two sorts informally

Count comparisons to compare the algorithms informally. The starting order matters for insertion sort but not for selection sort.

```
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;
}

int[] sorted = {1, 2, 3, 4, 5, 6};
int[] reversed = {6, 5, 4, 3, 2, 1};
System.out.println("selection, sorted:   " + selectionComparisons(new int[] {1, 2, 3, 4, 5, 6}));
System.out.println("selection, reversed: " + selectionComparisons(new int[] {6, 5, 4, 3, 2, 1}));
System.out.println("insertion, sorted:   " + insertionComparisons(sorted));
System.out.println("insertion, reversed: " + insertionComparisons(reversed));
```

Output:

```
selection, sorted:   15
selection, reversed: 15
insertion, sorted:   5
insertion, reversed: 15
```

(The `break` statement here only makes counting easy; it is not needed for the AP® exam.)

|  | Selection sort | Insertion sort |
| --- | --- | --- |
| Each pass | select the minimum of the unsorted portion, swap it in | insert the next element, shifting larger ones right |
| Is the position final after the pass? | yes 4.15.A.2 | not necessarily 4.15.A.3 |
| Comparisons, 6 elements already sorted | 15 | 5 |
| Comparisons, 6 elements in reverse order | 15 | 15 |
| Comparisons, n elements | always n(n - 1) / 2 | from n - 1 up to n(n - 1) / 2 |

Topic 4.17 adds a third sort, merge sort, which is recursive.

## Common mix-ups

- Not true: After k passes of insertion sort, the k smallest elements of the whole list are in place. That is true for selection sort. Insertion sort only sorts the first k + 1 elements among themselves; a smaller element later in the list can still push them right.
- Not true: Selection sort finishes early when the list is already sorted. Selection sort always scans the whole unsorted portion to be sure it has the minimum, so it makes the same number of comparisons for any order of n elements.
- Not true: Insertion sort swaps the new element with its neighbor over and over. Insertion sort saves the new element, shifts each larger sorted element one place right, then drops the saved element into the gap.

## In 30 seconds

- Both sorts are iterative: a loop of passes, each pass grows the sorted portion by one element.
- Selection sort: find the minimum of the unsorted portion and swap it into the next position; that position is final.
- Insertion sort: take the next unsorted element, shift larger sorted elements right, and insert it; positions can still change.
- Selection sort makes n(n - 1) / 2 comparisons for n elements, whatever the starting order.
- Insertion sort makes about n - 1 comparisons on sorted data and n(n - 1) / 2 on data in reverse order.

## Checkpoint: 5 practice questions

### Question 1

The following code segment performs the first two passes of selection sort on `arr`. What is printed as a result of executing the code segment?

```java
int[] arr = {5, 1, 4, 2, 8, 3};
for (int i = 0; i < 2; 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;
}
for (int v : arr)
{
    System.out.print(v + " ");
}
```

- A. 1 2 4 5 8 3
- B. 1 4 5 2 8 3
- C. 1 2 3 4 5 8
- D. 1 5 4 2 8 3

**Answer: A.** Pass 1 finds the minimum 1 and swaps it with 5: 1 5 4 2 8 3. Pass 2 finds the minimum of the unsorted portion, 2, and swaps it with 5: 1 2 4 5 8 3. 1 4 5 2 8 3 is the result of two passes of insertion sort, 1 5 4 2 8 3 stops after one pass, and 1 2 3 4 5 8 is the fully sorted array.

### Question 2

The following code segment performs the first three passes of insertion sort on `arr`. What is printed as a result of executing the code segment?

```java
int[] arr = {6, 3, 8, 1, 5};
for (int i = 1; i <= 3; 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;
}
for (int v : arr)
{
    System.out.print(v + " ");
}
```

- A. 1 3 5 6 8
- B. 1 3 8 6 5
- C. 1 3 6 8 5
- D. 3 6 8 1 5

**Answer: C.** Pass 1 inserts 3 before 6 (3 6 8 1 5), pass 2 leaves 8 in place, and pass 3 shifts 8, 6 and 3 right to insert 1 at the front: 1 3 6 8 5. 3 6 8 1 5 stops after two passes, 1 3 8 6 5 is selection sort after two passes, and 1 3 5 6 8 is fully sorted.

### Question 3

Which of the following statements about selection sort and insertion sort is true?

- A. After each pass of insertion sort, one more element is in its final position.
- B. Selection sort shifts elements of the sorted portion to make room.
- C. Insertion sort can only sort arrays, not ArrayList objects.
- D. After each pass of selection sort, one more element is in its final position.

**Answer: D.** Selection sort swaps the smallest unsorted element into the next position, and that position never changes again. Insertion sort places an element in its correct but not necessarily final position, because a smaller element found later can push it right. Shifting is how insertion sort works, not selection sort, and both sorts work on arrays and ArrayList objects.

### Question 4

Selection sort is used to sort an array of 8 integers that are already in increasing order. How many times is the comparison `arr[j] < arr[minIndex]` evaluated?

- A. 8
- B. 28
- C. 64
- D. 7

**Answer: B.** Selection sort scans the whole unsorted portion on every pass, whatever the order: 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 comparisons, which is n(n - 1) / 2 for n = 8. 7 is the number of passes, and 8 and 64 confuse the count with n and n squared. Only insertion sort finishes faster on sorted data.

### Question 5

The following code segment performs the first two passes of insertion sort on an `ArrayList`. What is printed as a result of executing the code segment?

```java
ArrayList<String> fruit = new ArrayList<String>();
fruit.add("pear");
fruit.add("fig");
fruit.add("kiwi");
fruit.add("apple");
for (int i = 1; i <= 2; i++)
{
    String key = fruit.get(i);
    int j = i - 1;
    while (j >= 0 && fruit.get(j).compareTo(key) > 0)
    {
        fruit.set(j + 1, fruit.get(j));
        j--;
    }
    fruit.set(j + 1, key);
}
System.out.println(fruit);
```

- A. [fig, pear, kiwi, apple]
- B. [fig, kiwi, pear, apple]
- C. [apple, fig, kiwi, pear]
- D. [fig, kiwi, apple, pear]

**Answer: B.** Pass 1 inserts "fig" before "pear": [fig, pear, kiwi, apple]. Pass 2 shifts "pear" right and inserts "kiwi" after "fig": [fig, kiwi, pear, apple]. [fig, pear, kiwi, apple] stops after one pass, and [apple, fig, kiwi, pear] is the fully sorted list (also the result of two selection sort passes).

## Questions students ask

**What is the difference between selection sort and insertion sort?**

Selection sort searches the unsorted portion for the smallest element and swaps it into its final place. Insertion sort takes the next element and inserts it into the sorted portion by shifting larger elements, so earlier elements can still move.

**How many passes does selection sort need?**

For n elements, selection sort and insertion sort both need n - 1 passes of the outer loop. After the last pass the remaining element is already in place.

**Which sort is faster, selection or insertion?**

On nearly sorted data insertion sort makes far fewer comparisons, because each new element stops early. Selection sort makes the same number of comparisons for every order. On the AP® exam you compare them informally by counting steps.

**Do you need to write sorting code on the AP® Computer Science A exam?**

Topic 4.15 asks you to determine the result of each step of selection sort and insertion sort, so be ready to trace the array after any pass and to recognize the code of each algorithm.

---

© LockInCS, licensed CC BY-NC-ND 4.0. AP® is a trademark registered by the College Board, which is not affiliated with, and does not endorse, this website.