Probleme – Le tri par tas, en place et en $\Theta (n\log n)$

1. Le tassage d'un élément.

/* Fait descendre t[i] jusqu'à sa place, en supposant que les sous-arbres
   enracinés en 2i+1 et 2i+2 vérifient déjà l'invariant de tas MAXIMUM.
   Postcondition : le sous-arbre enraciné en i vérifie l'invariant.
   Précondition : 0 <= i < n <= taille du tableau. */
void entasser(int t[], int n, int i) {
    assert(0 <= i && i < n);
    while (1) {
        int g = 2 * i + 1, d = 2 * i + 2, plus_grand = i;
        if (g < n && t[g] > t[plus_grand]) { plus_grand = g; }
        if (d < n && t[d] > t[plus_grand]) { plus_grand = d; }
        if (plus_grand == i) { return; }        /* la place est trouvée */
        int tmp = t[i]; t[i] = t[plus_grand]; t[plus_grand] = tmp;
        i = plus_grand;
    }
}

Terminaison : le variant est $\lfloor {\log }_{2}n\rfloor -\lfloor {\log }_2(i+1)\rfloor$, c'est-à-dire le nombre de niveaux sous $i$ ; à chaque tour $i$ est remplacé par un de ses fils, donc descend d'un niveau. La boucle fait au plus $h$ tours. Correction : après l'échange, le plus grand des trois est en $i$, donc l'invariant tient en $i$ ; le seul endroit où il peut être rompu est la nouvelle position, et c'est précisément là qu'on continue. Complexité : $O(h-\text{profondeur}(i))$, donc $O(\log n)$ au pire, et $2$ comparaisons par niveau.

2. La construction, et son coût linéaire.

/* Transforme le tableau t de n éléments en un tas MAXIMUM, EN PLACE.
   Complexité : Theta(n). Mémoire supplémentaire : O(1). */
void construire(int t[], int n) {
    /* INVARIANT : tous les sous-arbres enracinés en i+1, ..., n-1 sont des tas. */
    for (int i = n / 2 - 1; i >= 0; i = i - 1) { entasser(t, n, i); }
}

Pourquoi partir de $n/2-1$ : les indices $\lfloor n/2\rfloor$ à $n-1$ sont les feuilles, et une feuille est un tas à elle seule. L'invariant est donc vrai avant le premier tour. Conservation : au tour $i$, les sous-arbres de $2i+1$ et $2i+2$ sont des tas par l'invariant — ce sont des indices supérieurs à $i$ —, donc entasser s'applique et rend le sous-arbre de $i$ valide. Terminaison : le variant est $i$, qui décroît. À la sortie, $i=-1$ : tous les sous-arbres, dont celui de la racine, sont des tas.

Le coût. L'analyse naïve — $n/2$ appels à $O(\log n)$ — donne $O(n\log n)$ et surestime. Le point est que entasser coûte la hauteur sous $i$, pas la hauteur de l'arbre : les nœuds nombreux sont les moins chers. Un arbre complet à $n$ nœuds compte au plus $\lceil n/2^{k+1}\rceil$ nœuds de hauteur $k$, d'où

$$\sum _{k=0}^{\lfloor {\log }_{2}n\rfloor }\frac{n}{2^{k+1}}\cdot ck=\frac{cn}{2}\sum _{k\ge 0}\frac{k}{2^k}=\frac{cn}{2}\cdot 2=cn=\Theta (n),$$

en employant ${\sum }_{k\ge 0}k{x}^k=x/(1-x{)}^2$, qui vaut $2$ en $x=1/2$. C'est la convergence de cette série qui rend la construction linéaire, et c'est le seul point du calcul qui compte.

3. Le tri en place.

/* Trie t par ordre CROISSANT, en place. Complexité : Theta(n log n) dans TOUS
   les cas. Mémoire supplémentaire : O(1). */
void tri_par_tas(int t[], int n) {
    construire(t, n);                       /* tas MAXIMUM : le plus grand en t[0] */
    /* INVARIANT : t[j+1..n-1] contient les n-1-j plus grands éléments, TRIÉS,
       et t[0..j] est un tas maximum. */
    for (int j = n - 1; j >= 1; j = j - 1) {
        int tmp = t[0]; t[0] = t[j]; t[j] = tmp;   /* le maximum à sa place */
        entasser(t, j, 0);                         /* on rétablit sur t[0..j-1] */
    }
}

Pourquoi un tas MAXIMUM pour un tri croissant : c'est la clé du procédé. Le maximum sort en premier, et on le range à la fin — c'est-à-dire dans la case que l'on vient de libérer. Un tas minimum obligerait à ranger le minimum au début, où il faudrait décaler tout le reste. Le tas maximum et l'ordre croissant vont ensemble parce que la zone triée grandit par la droite.

Correction : à l'initialisation $j=n-1$, la zone triée est vide et $t[\mathrm{0..}n-1]$ est un tas ; conservation : $t[0]$ est le maximum de $t[\mathrm{0..}j]$, donc son rang est exactement $j$ dans le tableau final, et entasser(t, j, 0) rétablit l'invariant de tas sur $t[\mathrm{0..}j-1]$ ; terminaison : le variant est $j$, la boucle fait $n-1$ tours. À la sortie $j=0$ : $t[\mathrm{1..}n-1]$ est trié et $t[0]$ est le plus petit.

Complexité : $\Theta (n)$ pour la construction, puis $n-1$ tassages à $O(\log n)$ : $\Theta (n\log n)$ dans tous les cas, meilleur comme pire. Mémoire supplémentaire : trois entiers, soit $O(1)$.

4. Les mesures. Mesuré en OCaml sur des entiers tirés uniformément :

Les deux colonnes croissent linéairement, et le rapport reste à $1,21$. Sur des données aléatoires, les $n$ insertions sont linéaires elles aussi — la remontée moyenne est bornée. La séparation n'apparaît qu'au pire cas : mesuré sur une suite décroissante insérée dans un tas minimum, à $n=10^6$, les insertions demandent $17951445$ comparaisons contre $1999974$ pour le tassage, soit un facteur $9$ — et ce facteur croît en $\log n$.

Le tassage, lui, coûte $1,88n$ comparaisons et $0,74n$ échanges, quelles que soient les données : mesuré de $n=10^3$ à $n=10^6$, ces deux constantes ne bougent pas. Le tri complet, lui, demande $1,85n{\log }_{2}n$ comparaisons à $n=10^6$, et le tableau ressort trié — vérifié contre Array.sort.