Selection Sort

A simple O(n²) sorting algorithm with predictable behavior — and consistently poor performance.

Context

Selection sort is often taught alongside bubble and insertion sort.

Unlike them, it:

• does the same amount of work regardless of input,
• does not benefit from partial order,
• is easy to reason about, but rarely useful.

Core idea

• treat the prefix [0..i) as sorted
• scan the remaining suffix to find the smallest element
• swap it into position i
• repeat until the array is sorted

Each iteration fixes exactly one element.

Properties

• Time complexity:
  • Best / average / worst: O(n²) (no early exit, no adaptivity)
• Space complexity: O(1) (in-place)
• Not stable: Swapping can reorder equal elements.
• Minimal writes: exactly n − 1 swaps in the worst case.

Implementation

class SelectionSort {
    void sort(int[] array) {
        for (var i = 0; i < array.length; i++) {
            var minIndex = i;
            
            for (var j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            
            if (minIndex != i) {
                var temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
            }
        }
    }
}