Sorting Algorithms

⚠ Optional chapter.

Why Sort at All

Binary search (Lesson 28.1) needs sorted data to work, and sorted match-scouting data, sensor logs, or leaderboard scores are simply easier for a human to read. Two straightforward sorting algorithms cover the core idea; a third, more efficient one (merge sort) is covered in Lesson 28.4.

Selection Sort

Selection sort repeatedly finds the smallest remaining value and swaps it into its correct, final position — first position 0, then position 1, and so on:

public static void selectionSort(double[] sensorReadings)
{
    for (int j = 0; j < sensorReadings.length - 1; j++)
    {
        int minIndex = j; // assume the current position holds the smallest remaining value
        for (int k = j + 1; k < sensorReadings.length; k++)
        {
            if (sensorReadings[k] < sensorReadings[minIndex])
            {
                minIndex = k; // found something smaller — remember its index
            }
        }
        double temp = sensorReadings[j];
        sensorReadings[j] = sensorReadings[minIndex];
        sensorReadings[minIndex] = temp;
    }
}

This is the exact findMin pattern from Ch.9.5, done once per position: the outer loop tracks which position is being filled next; the inner loop always starts at j + 1, since everything before j is already sorted and shouldn't be re-scanned.

Selection sort takes the same amount of work regardless of the data's initial order — it always scans the entire unsorted remainder to find the minimum, every single pass.

Insertion Sort

Insertion sort instead takes each element and inserts it into its correct position among the already-sorted elements to its left, shifting larger values right to make room:

public static void insertionSort(double[] sensorReadings)
{
    for (int j = 1; j < sensorReadings.length; j++)
    {
        double temp = sensorReadings[j];
        int possibleIndex = j;
        while (possibleIndex > 0 && temp < sensorReadings[possibleIndex - 1])
        {
            sensorReadings[possibleIndex] = sensorReadings[possibleIndex - 1]; // shift right
            possibleIndex--;
        }
        sensorReadings[possibleIndex] = temp; // place temp in its final spot for this pass
    }
}

Unlike selection sort, insertion sort is adaptive — if the data is already (or nearly) sorted, the while loop's condition fails almost immediately for most elements, doing very little actual shifting. Data that's already sorted descending is insertion sort's worst case, since every element has to shift all the way to the front.

Comparing the Two

Both algorithms have similar overall growth (roughly n² comparisons for n elements, in the worst case) — but they behave differently depending on the input:

Common Pitfalls

• Starting selection sort's inner loop at index 0 instead of j + 1. That re-scans (and can undo) already-correctly-placed elements from earlier passes.
• Stopping insertion sort's outer loop one element too early. The loop must run through the entire array (j < length), not length - 1, or the very last element never gets inserted into its sorted position.
• Assuming either algorithm's runtime depends on input order the same way. Selection sort's cost is fixed regardless of order; insertion sort's genuinely isn't — that's the entire point of calling it adaptive.

Key Takeaways

• Selection sort repeatedly finds the minimum of the remaining unsorted portion and swaps it into place — same cost regardless of initial order.
• Insertion sort inserts each element into its correct position among already-sorted elements to its left, shifting as needed — adaptive, much faster on nearly-sorted data.
• Both run roughly n² in the worst case, but real-world performance can differ significantly depending on how sorted the input already is.
• Sorted data unlocks binary search (Lesson 28.1) — one reason sorting matters beyond just readability.

Derived from csawesome-2026: unit-4-data-collections/4.15-sorting-algorithms.md (CSA 4.15)