Les tris

Trier un tableau, c'est réorganiser ses valeurs par ordre croissant. Le tri est partout : pour chercher par dichotomie (chapitre 12), pour détecter des doublons, pour afficher, pour fusionner des fichiers… C'est aussi un formidable terrain d'exercice : les quatre algorithmes de ce chapitre illustrent chacun une méthode du livre.

Notation : pour deux sous-tableaux, on écrit $T[a:b]\le T[c:d]$ si toute valeur du premier est inférieure ou égale à toute valeur du second.

14.1 Tri par insertion

C'est le tri du joueur de cartes : on prend les cartes une à une et on insère chacune à sa place parmi celles déjà en main, qui sont triées.

Invariant.

$I(k)$ : « $T[0:k]$ est trié (et contient les $k$ premières valeurs initiales) ».

• Initialisation : $I(1)$ est vraie, un tableau d'une case est trié.
• Progression : on insère $T[k]$ dans le préfixe trié $T[0:k]$ par la recherche arrière du chapitre 12 : $I(k)$ et $k\ne n$ $\Rightarrow$ $I(k+1)$ après insertion.
• Arrêt : $I(n)$, le tableau entier est trié.

static void triInsertion(int[] T) { int n = T.length;
    // I(k) : T[0:k] est trié (et contient les k premières valeurs initiales)
    for (int k = 1; k < n; k++) {      // I(1) : un 1-préfixe est trié
        int x = T[k], j = k;
        // J(j) : T[0:j] et T[j+1:k+1] triés, T[j+1:k+1] > x, case j libre
        while (j > 0 && T[j-1] > x) { T[j] = T[j-1]; j--; }
        T[j] = x;                      // I(k+1)
    }
    // I(n) : T[0:n] est trié
}

Complexité.

L'insertion de $T[k]$ fait au plus $k$ décalages.

• Pire cas (tableau trié par ordre décroissant) : chaque valeur traverse tout le préfixe, $1+2+\cdots +(n-1)=n(n-1)/2$ décalages : $\Theta (n^2)$.
• Meilleur cas (tableau déjà trié) : aucun décalage, un seul test par valeur : $\Theta (n)$.
• En moyenne (valeurs dans un ordre aléatoire) : chaque valeur traverse la moitié du préfixe, environ $n^2/4$ décalages : $\Theta (n^2)$.

14.2 Tri par fusion

Le tri par fusion (merge sort, John von Neumann, 1945) est l'exemple type du « diviser pour régner » (chapitre 13) :

• couper $T[i:j]$ en deux moitiés $T[i:k]$ et $T[k:j]$ ;
• trier récursivement chaque moitié ;
• fusionner les deux moitiés triées.

static void triFusion(int[] T) { triFusion(T, 0, T.length, new int[T.length]); }

static void triFusion(int[] T, int i, int j, int[] B) { // trie T[i:j]
    if (j - i <= 1) return;            // 0 ou 1 valeur : T[i:j] trié
    int k = (i + j) / 2;
    triFusion(T, i, k, B);             // T[i:k] trié
    triFusion(T, k, j, B);             // T[k:j] trié
    fusionner(T, i, k, j, B);          // T[i:j] trié
}

14.2.1 La fusion

Deux sous-tableaux triés $T[i:k]$ et $T[k:j]$ sont donnés. On construit leur fusion triée dans un tableau de travail $B$, en prenant à chaque étape la plus petite des deux valeurs de tête.

Invariant de la fusion.

$I(p,q,r)$ : « $B[i:r]$ est la fusion triée de $T[i:p]$ et $T[k:q]$, et $B[i:r]\le T[p:k]$, $B[i:r]\le T[q:j]$ ». Comme $r=i+(p-i)+(q-k)$, chaque tour place une valeur.

static void fusionner(int[] T, int i, int k, int j, int[] B) {
    int p = i, q = k, r = i;
    // I(p,q,r) : B[i:r] est la fusion triée de T[i:p] et T[k:q],
    //            et B[i:r] <= T[p:k], B[i:r] <= T[q:j]
    while (p < k && q < j)
        if (T[p] <= T[q]) B[r++] = T[p++];   // <= : le tri est stable
        else              B[r++] = T[q++];
    while (p < k) B[r++] = T[p++];      // reste de T[i:k]
    while (q < j) B[r++] = T[q++];      // reste de T[k:j]
    for (r = i; r < j; r++) T[r] = B[r];
}