Selection Sort Explained — How It Works, Code & Complexity

public class SelectionSortTrace {

    public static void main(String[] args) {
        int[] numbers = {64, 25, 12, 22, 11};

        System.out.println("=== Selection Sort — Trace Mode ===");
        System.out.print("Original array: ");
        printArray(numbers);
        System.out.println();

        int arrayLength = numbers.length;

        // Outer loop: moves the 'sorted boundary' forward one step each pass
        for (int sortedBoundary = 0; sortedBoundary < arrayLength - 1; sortedBoundary++) {

            // Assume the first element in the unsorted region is the minimum
            int minIndex = sortedBoundary;

            // Inner loop: scan the entire unsorted region to find the true minimum
            for (int scanner = sortedBoundary + 1; scanner < arrayLength; scanner++) {
                if (numbers[scanner] < numbers[minIndex]) {
                    minIndex = scanner; // Found a new minimum — update the index
                }
            }

            // Only swap if the minimum isn't already in the correct position
            if (minIndex != sortedBoundary) {
                int temp = numbers[sortedBoundary];       // Save the value being displaced
                numbers[sortedBoundary] = numbers[minIndex]; // Move minimum to sorted boundary
                numbers[minIndex] = temp;                 // Put displaced value where minimum was
            }

            // Print the array after each pass so we can watch the sort happen
            System.out.print("After pass " + (sortedBoundary + 1) + ":       ");
            printArray(numbers);
            System.out.println("  (positions 0-" + sortedBoundary + " sorted)");
        }

        System.out.println();
        System.out.print("Final sorted array: ");
        printArray(numbers);
    }

    // Helper method to print an array in a readable format
    static void printArray(int[] array) {
        System.out.print("[");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if (i < array.length - 1) System.out.print(", ");
        }
        System.out.print("]");
    }
}

public class ComplexityDemo {

    public static void main(String[] args) {
        // Demonstrates that comparison count matches n*(n-1)/2 exactly
        int[] testSizes = {5, 10, 20, 50};

        System.out.println("=== Selection Sort Comparison Count vs n*(n-1)/2 ===");
        System.out.printf("%-12s %-20s %-20s%n", "Array Size", "Actual Comparisons", "Formula n*(n-1)/2");
        System.out.println("-".repeat(55));

        for (int size : testSizes) {
            // Build a worst-case (reverse-sorted) array of this size
            int[] reverseArray = new int[size];
            for (int i = 0; i < size; i++) {
                reverseArray[i] = size - i; // [5,4,3,2,1] for size 5
            }

            long comparisonCount = countComparisons(reverseArray);
            long formulaResult = (long) size * (size - 1) / 2;

            System.out.printf("%-12d %-20d %-20d%n", size, comparisonCount, formulaResult);
        }

        System.out.println();
        System.out.println("Key insight: comparisons match EXACTLY — selection sort");
        System.out.println("always does n*(n-1)/2 comparisons, no matter the input order.");
    }

    // Runs selection sort and counts every comparison made
    static long countComparisons(int[] array) {
        int[] copy = array.clone(); // Work on a copy so we don't modify the original
        long comparisons = 0;
        int length = copy.length;

        for (int sortedBoundary = 0; sortedBoundary < length - 1; sortedBoundary++) {
            int minIndex = sortedBoundary;
            for (int scanner = sortedBoundary + 1; scanner < length; scanner++) {
                comparisons++; // Count every time we compare two elements
                if (copy[scanner] < copy[minIndex]) {
                    minIndex = scanner;
                }
            }
            // Perform the swap
            int temp = copy[sortedBoundary];
            copy[sortedBoundary] = copy[minIndex];
            copy[minIndex] = temp;
        }
        return comparisons;
    }
}

public class GotchasFixed {

    public static void main(String[] args) {
        int[] original = {29, 10, 14, 37, 13};

        System.out.println("=== Demonstrating All Three Gotchas ===");
        System.out.print("Original array before sorting: ");
        printArray(original);

        // GOTCHA 3 FIX: Sort a clone so the original is preserved
        int[] sorted = selectionSort(original.clone());

        System.out.print("\nOriginal array after sorting:  ");
        printArray(original); // Should be unchanged
        System.out.print("\nSorted copy:                   ");
        printArray(sorted);
    }

    static int[] selectionSort(int[] array) {
        int length = array.length;

        // GOTCHA 1 FIX: outer loop goes to length-1, not length
        // When one element remains in the unsorted region, it's already in place
        for (int sortedBoundary = 0; sortedBoundary < length - 1; sortedBoundary++) {
            int minIndex = sortedBoundary;

            for (int scanner = sortedBoundary + 1; scanner < length; scanner++) {
                if (array[scanner] < array[minIndex]) {
                    minIndex = scanner;
                }
            }

            // GOTCHA 2 FIX: only swap when the minimum is NOT already in position
            // This avoids a pointless write operation and preserves relative order
            // in cases where the same value appears more than once
            if (minIndex != sortedBoundary) {
                int displaced = array[sortedBoundary];
                array[sortedBoundary] = array[minIndex];
                array[minIndex] = displaced;
            }
        }
        return array;
    }

    static void printArray(int[] array) {
        System.out.print("[");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if (i < array.length - 1) System.out.print(", ");
        }
        System.out.println("]");
    }
}