Selection Sort

After this lesson, you will be able to:

• Explain the selection sort algorithm in plain English
• Trace selection sort pass by pass, showing the array after each swap
• Implement selection sort with nested loops and a swap using a temp variable
• Explain why selection sort is O(n²) and when that matters
• Perform the three-step swap pattern with a temporary variable

The Sorting Problem

Yesterday you learned binary search — but it only works on sorted data. How do you sort an unsorted array? Today you learn selection sort, the simplest sorting algorithm to understand and the one Dr. Steiner uses as the standard in this course.

From CSCD 110: In Python, you called sorted(my_list) and Python handled everything. In Java, you can use Arrays.sort(), but this course requires you to understand how sorting works. Selection sort is the algorithm you are expected to implement by hand.

The Idea

Selection sort works like organizing a hand of cards:

1. Find the smallest card in your unsorted hand
2. Swap it with the first unsorted position
3. The sorted portion grows by one. Repeat.

After pass k, the first k elements are in their final sorted positions — they will never move again.

The Three-Step Swap

Before we sort, we need to swap two elements. You cannot just write a = b; b = a; — that loses the original value of a. Use a temporary variable:

// Swap arr[i] and arr[j]
int temp = arr[i];     // 1. save arr[i]
arr[i] = arr[j];       // 2. overwrite arr[i] with arr[j]
arr[j] = temp;         // 3. restore saved value to arr[j]

Common Pitfall: Without the temp variable, one value is lost. This is the standard swap pattern used throughout Java (and C, C++, etc.).

Pass-by-Pass Tracing

Understanding what happens after each pass is more important than the code. Starting array: {64, 25, 12, 22, 11}

After 4 passes, all 5 elements are sorted. (An array of n elements needs n - 1 passes.)

Pass 1: [64, 25, 12, 22, 11]  →  [11 | 25, 12, 22, 64]
          ↑ sorted ──────────┘     ↑ sorted
Pass 2: [11, 25, 12, 22, 64]  →  [11, 12 | 25, 22, 64]
Pass 3: [11, 12, 25, 22, 64]  →  [11, 12, 22 | 25, 64]
Pass 4: [11, 12, 22, 25, 64]  →  [11, 12, 22, 25 | 64]
                                   ↑ fully sorted ─────┘

Implementation

public static void selectionSort(final int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        // Find index of minimum in unsorted portion [i..end]
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // Swap minimum with position i
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

Walking through the code:

• Outer loop (i): represents the current pass. After pass i, elements 0 through i are sorted.
• Inner loop (j): scans the unsorted portion [i+1..end] to find the minimum.
• minIndex: tracks where the smallest unsorted element is.
• Swap: puts the minimum into position i.

Key Insight: The outer loop goes to arr.length - 1, not arr.length. When the first n-1 elements are in their correct positions, the last element must also be correct — there is nowhere else for it to go.

Complete Example: Sort and Display

import java.util.Arrays;
import java.util.Scanner;

public class SortScores {
    public static void selectionSort(final 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;
        }
    }

    public static void main(String[] args) {
        int[] scores = {78, 95, 62, 88, 73, 91, 85};

        System.out.println("Before: " + Arrays.toString(scores));
        selectionSort(scores);
        System.out.println("After:  " + Arrays.toString(scores));
    }
}

Output:

Before: [78, 95, 62, 88, 73, 91, 85]
After:  [62, 73, 78, 85, 88, 91, 95]

Notice that selectionSort modifies the array directly — it does not return a new array. This works because arrays are reference types (Lesson 2.1).

How Many Operations?

For an array of n elements:

• Pass 1: scan n - 1 elements
• Pass 2: scan n - 2 elements
• Pass 3: scan n - 3 elements
• …
• Pass n - 1: scan 1 element

Total comparisons: (n-1) + (n-2) + … + 1 = n(n-1)/2 ≈ n²/2

Selection sort is O(n²). Double the data size, and sorting takes roughly 4x longer. For small arrays this is fine. For large arrays (millions of elements), faster algorithms like merge sort — O(n log n) — are needed. You will learn those in CSCD 300.

Summary

Selection sort finds the minimum in the unsorted portion and swaps it into the next sorted position. After k passes, the first k elements are in their final positions.

The three-step swap uses a temporary variable: save, overwrite, restore. The algorithm needs n-1 passes and performs O(n²) comparisons total.

Selection sort is simple, predictable, and always makes exactly n-1 swaps. It is the standard sorting algorithm for this course.

Next lesson: Arrays and methods — passing arrays to methods, reference semantics, and memory diagrams showing stack and heap.