Topic 4.15 Notes – Sorting Algorithms

What Sorting Algorithms Do

Sorting means rearranging elements so they follow a consistent order based on comparisons like < or > (or accessor-based comparisons for objects).

Both selection sort and insertion sort:

• Work on arrays or ArrayList
• Use loops, not recursion
• Compare elements directly
• Divide the structure into:
  • A sorted portion
  • An unsorted portion
• Grow the sorted portion by one element per outer loop pass

Here’s the mental model you should always have. The example below shows selection sort building a sorted portion one step at a time.

Selection sort growing the sorted portion

After each outer loop pass, one more element moves into the sorted side.

The difference is how that element gets there.

Selection Sort

The Core Idea

Selection sort repeatedly finds the smallest element in the unsorted portion and swaps it into its final position.

After pass i, index i contains the correct value permanently.

How It Works Step by Step

For an array of length n:

1. Outer loop runs i = 0 to n - 2
2. Assume minIndex = i
3. Inner loop checks elements from i + 1 to n - 1
4. If a smaller value is found, update minIndex
5. After the inner loop, swap arr[i] and arr[minIndex]

Here’s the classic structure:

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

What’s Always True

• After pass 0 → smallest element at index 0
• After pass 1 → second smallest at index 1
• Elements placed are in their final position

Selection sort makes the same number of comparisons no matter what the starting order is.

Recognition pattern on a test:

• Nested loops
• Inner loop searches for a minimum
• One swap per outer pass

Insertion Sort

The Core Idea

Insertion sort takes one element from the unsorted portion and inserts it into the correct spot inside the sorted portion by shifting elements right.

After pass i, indices 0 through i are sorted.

How It Works Step by Step

1. Outer loop starts at i = 1
2. Store key = arr[i]
3. Compare backward through sorted portion
4. Shift larger elements right
5. Insert key in the open spot

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];
        j--;
    }

    arr[j + 1] = key;
}

What’s Always True

• After pass 1 → first two elements sorted
• After pass k → indices 0..k sorted
• Elements shift instead of swapping far away

Insertion sort is stable. Equal elements keep their relative order.

It also runs much faster when the array is already mostly sorted. That shows up in multiple choice questions about efficiency.

Recognition pattern:

• Outer loop starting at 1
• key variable
• while (j >= 0 && ...)
• Shifting right

Selection vs Insertion

Here’s the conceptual difference that matters most:

If you’re tracing:

• Selection → ask “Which index is being finalized?”
• Insertion → ask “Where does this key slide into place?”

Tracing on Tests and the AP Exam

You’ll often be asked:

• What does the array look like after pass 2?
• How many swaps occur?
• Which algorithm is this?

When tracing:

1. Identify the algorithm first.
2. Track the outer loop index.
3. Rewrite the entire array after each pass.
4. Watch boundaries like j >= 0 and i < length - 1.

Common mistake I see every year:
Students think insertion sort places elements in final positions each time. It doesn’t. Later insertions can still shift earlier elements.

If you lock in the growth of the sorted portion, most tracing problems become mechanical.