Probleme – Le tri par insertion, deux fois

1. La version fonctionnelle.

(* insere x l : la liste l ou x a ete insere a sa place.
   Precondition  : l est triee par ordre croissant.
   Postcondition : le resultat est trie et contient exactement les
                   elements de l plus une occurrence de x. *)
let rec insere x l =
  match l with
  | [] -> [x]
  | t :: r -> if x <= t then x :: l else t :: insere x r

(* tri l : la liste des elements de l, triee par ordre croissant.
   Precondition : aucune. *)
let rec tri l =
  match l with
  | [] -> []
  | x :: r -> insere x (tri r)

Correction de insere, par induction sur la longueur de l. Si l est vide, [x] est trié et contient bien $x$. Sinon l = t :: r est triée, donc $t$ en est le minimum. Si $x\le t$, alors $x$ minore toute l et x :: l est triée. Sinon $x>t$, l'hypothèse d'induction donne insere x r triée et de contenu correct ; comme $t$ minore r et que $t<x$, il minore aussi insere x r, donc t :: insere x r est triée.

Correction de tri, par induction sur la longueur : tri r est triée par hypothèse, et insere préserve le tri et le contenu.

Terminaison : chaque appel porte sur une liste strictement plus courte ; la longueur est le variant.

2. La version impérative, en place.

(* Trie t par ordre croissant, en place. Precondition : aucune. *)
let tri_tableau t =
  let n = Array.length t in
  (* INVARIANT EXTERIEUR : t.(0) .. t.(i-1) est trie et contient les
     elements que ces cases contenaient au depart. *)
  for i = 1 to n - 1 do
    let v = t.(i) in
    let j = ref (i - 1) in
    (* INVARIANT INTERIEUR : les cases t.(!j+2) .. t.(i) contiennent les
       anciennes t.(!j+1) .. t.(i-1), toutes strictement superieures a v. *)
    while !j >= 0 && t.(!j) > v do
      t.(!j + 1) <- t.(!j);
      decr j
    done;
    t.(!j + 1) <- v
  done

Terminaison : variant $n-i$ pour la boucle extérieure, $j+1$ pour l'intérieure. Utilisation de l'invariant extérieur : à la sortie, $i=n$, donc tout le tableau est trié.

Noter que la condition !j >= 0 && t.(!j) > v range encore une fois la garde en premier : sans cela, t.(-1) lèverait Invalid_argument au premier élément qui doit aller en tête.

3. Le comptage des comparaisons d'éléments.

Meilleur cas, tableau déjà trié : la boucle intérieure échoue immédiatement, $1$ comparaison par tour, soit $n-1$ au total. Le tri par insertion est donc $\Theta (n)$ sur une entrée triée — propriété que peu de tris possèdent.

Pire cas, tableau strictement décroissant : le tour $i$ fait $i$ comparaisons, soit ${\sum }_{i=1}^{n-1}i=n(n-1)/2$.

Cas moyen : en moyenne, un élément se range au milieu de la partie triée, d'où environ $n(n-1)/4$.

La mesure, sur des entrées déjà triées, inversées, et tirées au hasard :

 n   |  trie  | inverse | aleatoire || n-1  | n(n-1)/2 | n(n-1)/4
 10  |     9  |     45  |      35   ||   9  |      45  |      22
 20  |    19  |    190  |      87   ||  19  |     190  |      95
 50  |    49  |   1225  |     600   ||  49  |    1225  |     612
100  |    99  |   4950  |    2821   ||  99  |    4950  |    2475
200  |   199  |  19900  |    9730   || 199  |   19900  |    9950

Les colonnes « trié » et « inversé » collent exactement aux formules — c'est le signe que le comptage mesure bien ce qu'on croit. La colonne aléatoire oscille autour de $n(n-1)/4$ : une espérance n'est pas une garantie, et une seule exécution ne la mesure pas.

4. Ce qui sépare les deux versions. Pas le temps : les deux sont $\Theta (n^2)$ dans le pire cas.

• L'espace. La version tableau trie en place : $\Theta (1)$ d'espace supplémentaire. La version liste alloue une cellule par :: construit, soit $\Theta (n^2)$ cellules allouées au total dans le pire cas — que le ramasse-miettes récupérera, mais qu'il aura fallu produire. Elle consomme de plus $\Theta (n)$ de pile.
• L'effet. La version tableau détruit son entrée ; la version liste rend une liste neuve et laisse l'ancienne intacte. Selon l'usage, l'un est un service et l'autre une nuisance, et c'est la spécification qui doit le dire.
• La preuve. L'une se prouve par induction structurelle en dix lignes ; l'autre demande deux invariants dont l'intérieur est délicat à énoncer correctement.

C'est l'illustration de la phrase du chapitre : « un algorithme qui ne survit pas au changement de langage n'était pas un algorithme ». Ici il survit — mais il change de coût en mémoire, et cela ne se lit pas dans le $\Theta (n^2)$.