Tris élémentaires

La leçon précédente s'est achevée sur une dette : la dichotomie exige un tableau trié. Il est temps de le trier. Les deux algorithmes de cette leçon ne sont pas les plus rapides — ils sont les plus instructifs, parce qu'on peut les dérouler entièrement à la main.

Ce que trier veut dire

Trier un tableau, c'est le réorganiser pour que T[0] ≤ T[1] ≤ … ≤ T[n − 1]. Deux exigences, pas une seule :

• l'ordre : chaque case est inférieure ou égale à la suivante ;
• la permutation : le tableau final contient exactement les mêmes valeurs que le tableau initial, ni plus, ni moins.

La seconde est facile à oublier, et c'est pourtant elle qui interdit les fausses solutions. Un algorithme qui remplirait le tableau de zéros produirait une suite parfaitement croissante — et un résultat évidemment faux.

Les deux tris qui suivent travaillent en place : ils réorganisent le tableau existant sans en créer un second. La seule opération dont ils disposent pour cela est l'échange de deux cases — exactement le schéma tmp de la leçon 2.

Le tri par sélection

L'idée tient en une phrase : chercher le plus petit élément restant, et l'amener à sa place définitive.

1Pour i de 0 à n − 2 Faire2    indiceMin ← i3    Pour j de i + 1 à n − 1 Faire4        Si T[j] < T[indiceMin] Alors5            indiceMin ← j6        FinSi7    FinPour8    tmp ← T[i]9    T[i] ← T[indiceMin]10    T[indiceMin] ← tmp11FinPour

Deux boucles imbriquées : celle de i compte les tours, celle de j cherche le minimum dans ce qui reste. On mémorise l'indice du minimum, pas sa valeur — c'est l'indice qui servira à échanger.

L'invariant de ce tri — la propriété vraie à la fin de chaque tour — est le suivant : après le tour i, les cases 0 à i contiennent les i + 1 plus petites valeurs, à leur place définitive. Définitive est le mot fort : ces cases ne bougeront plus jamais.

Remarquez aussi qu'on s'arrête à n − 2 : quand les n − 1 premières cases sont définitives, la dernière l'est forcément, puisqu'il ne reste qu'une valeur pour l'occuper.

Le tri par insertion

Autre idée, celle du joueur de cartes : prendre l'élément suivant et le glisser à sa place parmi ceux déjà rangés.

1Pour i de 1 à n − 1 Faire2    valeur ← T[i]3    j ← i − 14    TantQue j ≥ 0 ET T[j] > valeur Faire5        T[j + 1] ← T[j]6        j ← j − 17    FinTantQue8    T[j + 1] ← valeur9FinPour

La boucle démarre à 1, pas à 0 : une case seule est déjà triée, il n'y a rien à faire au premier élément. La boucle interne ne cherche pas, elle décale — chaque élément trop grand recule d'une case pour ouvrir un trou, et la valeur mise de côté vient s'y loger.

Un détail de la condition j ≥ 0 ET T[j] > valeur mérite l'attention : l'ordre des deux tests n'est pas indifférent. Le premier protège le second. Quand j atteint −1, la machine constate que j ≥ 0 est FAUX et n'évalue même pas T[j], ce qui serait un débordement d'indice. Cette évaluation paresseuse est garantie par tous les langages courants, mais elle vous impose de mettre le garde-fou en premier.

Comparer les deux sur le même tableau

Les deux animations partent du même tableau [5, 2, 9, 1, 6]. Rejouez-les côte à côte : le comportement diffère profondément.

La différence d'invariant est le point le plus important de la leçon. Dans le tri par sélection, une case placée ne bouge plus jamais : elle est définitive. Dans le tri par insertion, la partie gauche est triée mais pas définitive — regardez le 9 dans l'animation, il est encore déplacé au dernier tour.

À vous

// Complétez le tri par sélection.
// Rappel de l'invariant : après le tour i, les cases 0 à i sont à leur
// place DÉFINITIVE.
function triSelection(t) {
  const a = [...t]; // on travaille sur une copie, l'original reste intact

  for (let i = 0; i < a.length - 1; i++) {
    let indiceMin = i;

    for (let j = i + 1; j < a.length; j++) {
      // à compléter : retenir l'indice du plus petit élément restant
    }

    // à compléter : échanger a[i] et a[indiceMin]
  }

  return a;
}

console.log(triSelection([5, 2, 9, 1, 6]));  // attendu : [1, 2, 5, 6, 9]
console.log(triSelection([1, 2, 3]));        // attendu : [1, 2, 3]

function triSelection(t) {
  const a = [...t];

  for (let i = 0; i < a.length - 1; i++) {
    // On mémorise l'INDICE, pas la valeur : c'est lui qui servira à échanger.
    let indiceMin = i;

    for (let j = i + 1; j < a.length; j++) {
      if (a[j] < a[indiceMin]) indiceMin = j;
    }

    const tmp = a[i];
    a[i] = a[indiceMin];
    a[indiceMin] = tmp;
  }

  // n - 1 tours suffisent : la dernière case est forcément à sa place.
  return a;
}

console.log(triSelection([5, 2, 9, 1, 6]));
console.log(triSelection([1, 2, 3]));

À retenir