Selection sort: minimize writes, pay in comparisons

One swap per pass, many comparisons

Selection sort walks the array and, on each pass, finds the smallest remaining element and swaps it into position. It performs exactly n − 1 swaps total, which makes it attractive when writes are expensive — for instance, when the elements are very large and moving them is costly, or when storage has a high per-write cost (old Flash memory).

public static void selectionSort(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIdx]) minIdx = j;
        }
        if (minIdx != i) {
            int t = a[i]; a[i] = a[minIdx]; a[minIdx] = t;
        }
    }
}

Comparisons vs. writes

Comparisons are always Θ(n²) — there is no shortcut. Writes (swaps) are O(n). Memory is O(1). Selection sort is not stable in its simplest form, because the long-distance swap can reorder equal elements.