Tri par sélection

Invariant : « $T[0:k]$ est trié et $T[0:k]\le T[k:n]$ ». Il est vrai pour $k=0$. Le minimum de $T[k:n]$, placé en case $k$, est supérieur ou égal à $T[0:k]$ et inférieur ou égal au reste : on obtient l'invariant pour $k+1$. Pour $k=n-1$, la dernière case est le maximum : le tableau est trié.

nom : T
cases : 8
vert : 0..2
colorier : 6
fleches : 6->3
fleches-bas : 3->6
pointeurs : k=3 m=6
zone : 0..2 trié
zone : 3..7 à trier
legende : m : indice du minimum de T[k:n], échangé avec T[k]

static void triSelection(int[] T) { int n = T.length;
    // I(k) : T[0:k] est trié et T[0:k] <= T[k:n]
    for (int k = 0; k < n - 1; k++) {
        int m = k;                        // indice du minimum de T[k:n]
        for (int i = k + 1; i < n; i++) if (T[i] < T[m]) m = i;
        echanger(T, k, m);                // I(k+1)
    }
}

La recherche du minimum de $T[k:n]$ fait $n-k-1$ comparaisons, quel que soit le contenu du tableau : au total $(n-1)+(n-2)+\cdots +1=n(n-1)/2$ comparaisons, dans le pire et dans le meilleur cas. Le programme en compte $28$ pour $n=8$, sur un tableau quelconque comme sur un tableau trié : $\Theta (n^2)$ toujours, mais au plus $n-1$ échanges. Il n'est pas stable (corrigé de l'exercice 14.11).