Introduction

Sorting—arranging elements in a specific order—is another fundamental operation in computer science. Topic 4.15 introduces two iterative sorting algorithms: selection sort and insertion sort. Both algorithms work by gradually building a sorted portion of the collection.

Selection sort and insertion sort are iterative sorting algorithms that can be used to sort elements in an array or ArrayList. While neither is the most efficient sorting method for large datasets, they're simple to understand and demonstrate important algorithmic concepts. For the AP exam, you need to trace through these algorithms step-by-step, understanding how each iteration modifies the collection.

Selection Sort

Selection sort repeatedly selects the smallest (or largest) element from the unsorted portion of the list and swaps it into its correct (and final) position in the sorted portion of the list.

How Selection Sort Works

Think of sorting a hand of playing cards by repeatedly finding the lowest card in your unsorted pile and moving it to the end of your sorted pile.

Algorithm steps:

Find the minimum element in the unsorted portion
Swap it with the first element of the unsorted portion
The sorted portion grows by one element
Repeat until entire array is sorted

Selection Sort Example

Sort [64, 25, 12, 22, 11] in ascending order:

Initial: [64, 25, 12, 22, 11]

Unsorted: all elements

Pass 1: Find minimum in entire array

Minimum is 11 at index 4
Swap with index 0
Result: [11, 25, 12, 22, 64]
Sorted: [11] | Unsorted: [25, 12, 22, 64]

Pass 2: Find minimum in indices 1-4

Minimum is 12 at index 2
Swap with index 1
Result: [11, 12, 25, 22, 64]
Sorted: [11, 12] | Unsorted: [25, 22, 64]

Pass 3: Find minimum in indices 2-4

Minimum is 22 at index 3
Swap with index 2
Result: [11, 12, 22, 25, 64]
Sorted: [11, 12, 22] | Unsorted: [25, 64]

Pass 4: Find minimum in indices 3-4

Minimum is 25 at index 3 (already there)
No swap needed
Result: [11, 12, 22, 25, 64]
Sorted: [11, 12, 22, 25] | Unsorted: [64]

Final: [11, 12, 22, 25, 64] — fully sorted

Selection Sort Algorithm

Key characteristics:

Outer loop: tracks boundary between sorted and unsorted portions
Inner loop: finds minimum in unsorted portion
Each pass places one element in its final position
Number of passes: $n - 1$ where $n$ is array length

Tracing Selection Sort

For [29, 10, 14, 37, 13]:

$Pass Start 1234 Array State [29, 10, 14, 37, 13] [10, 29, 14, 37, 13] [10, 13, 14, 37, 29] [10, 13, 14, 37, 29] [10, 13, 14, 29, 37] Action - Found min 10, swapped with 29 Found min 13, swapped with 29 Found min 14, no swap needed Found min 29, swapped with 37$

Insertion Sort

Insertion sort inserts an element from the unsorted portion of a list into its correct (but not necessarily final) position in the sorted portion of the list by shifting elements of the sorted portion to make room for the new element.

How Insertion Sort Works

Think of sorting playing cards as you pick them up: you take each new card and insert it into its proper place among the cards you're already holding.

Algorithm steps:

Start with first element as "sorted portion"
Take next element from unsorted portion
Shift sorted elements right to make space
Insert the element in its correct position
Repeat until entire array is sorted

Insertion Sort Example

Sort [12, 11, 13, 5, 6] in ascending order:

Initial: [12, 11, 13, 5, 6]

Sorted: [12] | Unsorted: [11, 13, 5, 6]

Pass 1: Insert 11 into sorted portion

Compare 11 with 12: 11 < 12
Shift 12 right
Insert 11 at beginning
Result: [11, 12, 13, 5, 6]
Sorted: [11, 12] | Unsorted: [13, 5, 6]

Pass 2: Insert 13 into sorted portion

Compare 13 with 12: 13 > 12
13 is already in correct position
Result: [11, 12, 13, 5, 6]
Sorted: [11, 12, 13] | Unsorted: [5, 6]

Pass 3: Insert 5 into sorted portion

Compare 5 with 13: 5 < 13, shift 13 right
Compare 5 with 12: 5 < 12, shift 12 right
Compare 5 with 11: 5 < 11, shift 11 right
Insert 5 at beginning
Result: [5, 11, 12, 13, 6]
Sorted: [5, 11, 12, 13] | Unsorted: [6]

Pass 4: Insert 6 into sorted portion

Compare 6 with 13: 6 < 13, shift 13 right
Compare 6 with 12: 6 < 12, shift 12 right
Compare 6 with 11: 6 < 11, shift 11 right
Compare 6 with 5: 6 > 5, stop
Insert 6 after 5
Result: [5, 6, 11, 12, 13]

Final: [5, 6, 11, 12, 13] — fully sorted

Insertion Sort Algorithm

public static void insertionSort(int[] arr) 
{
    for (int i = 1; i < arr.length; i++) 
    {
        int key = arr[i];
        int j = i - 1;
        
        // Shift elements right to make space
        while (j >= 0 && arr[j] > key) 
        {
            arr[j + 1] = arr[j];
            j--;
        }
        
        // Insert key in correct position
        arr[j + 1] = key;
    }
}

Key characteristics:

Start from second element (index 1)
Inner loop shifts larger elements right
Insert current element in proper position
Elements left of current position are always sorted (but not in final positions)

Tracing Insertion Sort

For [8, 4, 2, 5, 1]:

$Pass Start 1234 Done Key - 4251 - Array State [8, 4, 2, 5, 1] [4, 8, 2, 5, 1] [2, 4, 8, 5, 1] [2, 4, 5, 8, 1] [1, 2, 4, 5, 8] [1, 2, 4, 5, 8] Action - Inserted 4 before 8 Inserted 2 at beginning Inserted 5 between 4 and 8 Inserted 1 at beginning Sorted$

Selection Sort vs Insertion Sort

$Aspect Strategy Position finality Best case Worst case Swaps Stable Selection Sort Find minimum, swap Elements reach final position Always n^{2} comparisons n^{2} comparisons Exactly (n - 1) swaps No Insertion Sort Insert element in place Elements may move again Nearly sorted: n comparisons Reverse sorted: n^{2} comparisons Variable (0 to n^{2}) Yes$

Stability: A sorting algorithm is stable if equal elements maintain their relative order. Insertion sort is stable; selection sort is not.

Sorting ArrayLists

Both algorithms work identically with ArrayLists, using ArrayList methods instead of array syntax:

Selection Sort for ArrayList

public static void selectionSort(ArrayList<Integer> list) 
{
    for (int i = 0; i < list.size() - 1; i++) 
    {
        int minIndex = i;
        for (int j = i + 1; j < list.size(); j++) 
        {
            if (list.get(j) < list.get(minIndex)) 
            {
                minIndex = j;
            }
        }
        
        // Swap using ArrayList methods
        int temp = list.get(i);
        list.set(i, list.get(minIndex));
        list.set(minIndex, temp);
    }
}

Insertion Sort for ArrayList

public static void insertionSort(ArrayList<Integer> list) 
{
    for (int i = 1; i < list.size(); i++) 
    {
        int key = list.get(i);
        int j = i - 1;
        
        while (j >= 0 && list.get(j) > key) 
        {
            list.set(j + 1, list.get(j));
            j--;
        }
        
        list.set(j + 1, key);
    }
}

Sorting Objects

To sort objects, modify the comparison:

// Sort students by GPA using selection sort
public static void sortByGPA(ArrayList<Student> students) 
{
    for (int i = 0; i < students.size() - 1; i++) 
    {
        int maxIndex = i;
        for (int j = i + 1; j < students.size(); j++) 
        {
            if (students.get(j).getGPA() > students.get(maxIndex).getGPA()) 
            {
                maxIndex = j;
            }
        }
        
        Student temp = students.get(i);
        students.set(i, students.get(maxIndex));
        students.set(maxIndex, temp);
    }
}

Common Mistakes

Mistake 1: Wrong loop bounds

// WRONG - outer loop should go to length-1
for (int i = 0; i < arr.length; i++) { }

Mistake 2: Swapping in insertion sort

// WRONG - insertion sort shifts, doesn't swap repeatedly
while (j >= 0 && arr[j] > key) 
{
    swap(arr, j, j+1);  // Inefficient
}

// CORRECT - shift elements
while (j >= 0 && arr[j] > key) 
{
    arr[j + 1] = arr[j];
    j--;
}

Mistake 3: Forgetting to store key in insertion sort

// WRONG - loses the value being inserted
for (int i = 1; i < arr.length; i++) 
{
    // Missing: int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > arr[i]) { }  // arr[i] changes!
}

FiveHive