Probleme – Le tri par sélection, prouvé et compté

1. Le code, annoté.

/* Trie les n premiers termes de t par ordre croissant, en place.
   Precondition  : n >= 0, et t a au moins n cases.
   Postcondition : t[0..n-1] est croissant et contient exactement les
                   memes valeurs qu'a l'appel (c'est une PERMUTATION). */
void tri_selection(int t[], int n) {
    assert(n >= 0);
    for (int i = 0; i < n - 1; i = i + 1) {
        /* INVARIANT EXTERIEUR : t[0..i-1] est trie, et tous ses termes
           sont <= a tous ceux de t[i..n-1]. */
        int mini = i;
        for (int j = i + 1; j < n; j = j + 1) {
            /* INVARIANT INTERIEUR : t[mini] est le plus petit de t[i..j-1]. */
            if (t[j] < t[mini]) { mini = j; }
        }
        int tmp = t[i]; t[i] = t[mini]; t[mini] = tmp;
    }
}

2. Les preuves.

Terminaison. Variant de la boucle intérieure : $n-j$, entier positif décroissant de $1$ par tour. Variant de la boucle extérieure : $n-1-i$, de même. Les deux boucles sont bornées, donc l'algorithme s'arrête après au plus $n(n-1)/2$ tours intérieurs.

Correction de la boucle intérieure. Initialisation : $j=i+1$ et $\text{mini}=i$, donc $t[\text{mini}]$ est bien le minimum de la tranche $t[i..i]$. Conservation : le corps remplace mini par $j$ exactement quand $t[j]$ est plus petit, donc $t[\text{mini}]$ reste le minimum de $t[i..j]$. Utilisation : à la sortie $j=n$, donc $t[\text{mini}]=\min t[i..n-1]$.

Correction de la boucle extérieure. Initialisation : $i=0$, la partie triée est vide, l'invariant est vrai par vacuité. Conservation : par ce qui précède, $t[\text{mini}]$ est le minimum de la partie non triée ; l'échange le place en position $i$. La partie $t[\mathrm{0..}i]$ reste triée — le nouveau terme est $\ge$ à tous les précédents par l'invariant, et $\le$ à tous les suivants puisque c'est leur minimum. Utilisation : à la sortie $i=n-1$, donc $t[\mathrm{0..}n-2]$ est trié et tous ses termes minorent $t[n-1]$ : le tableau entier est trié.

Et la permutation ? L'échange est la seule opération qui modifie $t$, et un échange préserve le multiensemble des valeurs. C'est la moitié de la postcondition qu'on oublie systématiquement d'énoncer — le problème 4.2 montre ce qu'elle coûte quand on l'omet.

3. Le comptage exact. La boucle intérieure fait $n-1-i$ comparaisons au tour $i$, quelles que soient les valeurs : il n'y a aucune sortie anticipée. Le total est

$$\sum _{i=0}^{n-2}(n-1-i)=\sum _{k=1}^{n-1}k=\frac{n(n-1)}{2},$$

et il y a exactement $n-1$ échanges. Mesuré sur trois familles d'entrées :

  n | croissant | decroissant | aleatoire | n(n-1)/2 | echanges | n-1
  5 |        10 |          10 |        10 |       10 |        4 |   4
 10 |        45 |          45 |        45 |       45 |        9 |   9
 50 |      1225 |        1225 |      1225 |     1225 |       49 |  49
100 |      4950 |        4950 |      4950 |     4950 |       99 |  99
500 |    124750 |      124750 |    124750 |   124750 |      499 | 499

Les trois colonnes sont identiques : meilleur cas, pire cas et cas moyen coïncident. Le tri par sélection est $\Theta (n^2)$ toujours, ce qui est rare et mérite d'être remarqué — l'analyse en cas moyen n'a ici rien à dire.

4. Sélection ou insertion.

Le tri par insertion est adaptatif : sur une entrée presque triée, il coûte $\Theta (n)$ — mesuré au problème 2.3. Le tri par sélection ne l'est jamais.

En revanche, le tri par sélection fait $\Theta (n)$ écritures, contre $\Theta (n^2)$ pour l'insertion. Si écrire coûte cher — mémoire flash, où chaque écriture use le support, ou éléments volumineux qu'on déplace bloc par bloc — c'est lui qui gagne. Le choix ne se lit pas dans le $\Theta (n^2)$ commun : il faut savoir quelle opération on compte.