Trier, partie 1 : tri à bulles, tri par sélection et tri par insertion

Le tri par sélection fait exactement 45 comparaisons sur n'importe quelle liste de 10 valeurs, qu'elle soit mélangée ou déjà dans l'ordre au départ.

Mettre les choses en ordre

Trier, c'est réorganiser une liste pour que ses valeurs aillent de la plus petite à la plus grande (ou par nom, date, prix, n'importe quel ordre qu'on peut comparer). C'est l'une des tâches les plus courantes d'un ordinateur : les contacts d'un téléphone, les résultats de recherche classés par pertinence, une colonne de tableur triée par date. Trier facilite aussi d'autres tâches. Comme l'a montré l'unité précédente, on peut chercher dans une liste triée avec la recherche dichotomique, et les doublons d'une liste triée se trouvent côte à côte.

Cette unité présente trois méthodes simples. Toutes trois comparent deux valeurs à la fois et déplacent les valeurs à l'intérieur de la même liste. Elles sont courtes à écrire et faciles à suivre, et toutes trois ralentissent fortement sur les longues listes. Comprendre pourquoi elles ralentissent est la meilleure préparation aux méthodes plus rapides de l'unité suivante. Tout au long, on compte deux choses : les comparaisons (se demander « cette valeur est-elle plus grande que celle-là ? ») et les échanges (permuter deux valeurs).

Le tri à bulles : échanger les voisins mal rangés

Le tri à bulles parcourt la liste en comparant chaque paire de voisins. Quand celui de gauche est plus grand, il les échange. Après un passage complet, la plus grande valeur a été transportée pas à pas tout à droite, comme une bulle qui remonte, et elle n'a plus jamais besoin de bouger. Le passage suivant peut s'arrêter une place plus tôt. Une amélioration courante consiste à guetter un passage sans aucun échange : cela signifie que tout est déjà dans l'ordre, et le tri peut s'arrêter plus tôt.

Suis-le sur la liste [5, 1, 4, 2, 8]. Le premier passage compare 5 et 1 (échange), 5 et 4 (échange), 5 et 2 (échange), 5 et 8 (on laisse) : la liste devient [1, 4, 2, 5, 8] et 8 est à sa place. Le deuxième passage compare 1 et 4, 4 et 2 (échange), 4 et 5, ce qui donne [1, 2, 4, 5, 8]. Le troisième passage compare 1 et 2, puis 2 et 4, ne fait aucun échange et s'arrête. Total : 4 + 3 + 2 = 9 comparaisons et 4 échanges.

function bubbleSort(a) {
  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;
    for (let j = 0; j < a.length - 1 - pass; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];  // échange
        swapped = true;
      }
    }
    if (!swapped) break;  // déjà triée
  }
  return a;
}

Le tri par sélection : trouver le plus petit, le placer ensuite

Le tri par sélection fonctionne comme beaucoup de gens trient une main de cartes. On parcourt toute la liste pour trouver la plus petite valeur et on l'échange avec la première position. Puis on parcourt le reste pour trouver la plus petite valeur restante et on l'échange avec la deuxième position, et ainsi de suite. Sur [5, 1, 4, 2, 8], le premier parcours trouve 1 et l'échange avec 5 ; le deuxième trouve 2 et l'échange avec 5 ; les deux derniers trouvent 4 et 5 déjà à leur place. Cela ne fait que 2 échanges, mais les parcours comparent quand même 4 + 3 + 2 + 1 = 10 fois.

Le tri par sélection ne s'arrête jamais plus tôt. Même sur une liste déjà triée, il doit vérifier toutes les valeurs restantes pour être sûr d'avoir la plus petite. Pour n valeurs, les comparaisons font toujours (n − 1) + (n − 2) + … + 1 = n(n − 1)/2. Pour 10 valeurs, cela fait 45 ; pour 100 valeurs, 4950 ; pour 1000 valeurs, 499 500. Son point fort est le petit nombre d'échanges : au plus n − 1, ce qui compte quand déplacer une valeur coûte cher.

Le tri par insertion : glisser chaque nouvelle valeur à sa place

Le tri par insertion garde la partie gauche de la liste triée et l'agrandit d'une valeur à la fois. Il prend la valeur suivante et la déplace vers la gauche, en l'échangeant avec sa voisine, jusqu'à ce que la voisine ne soit plus plus grande. Cette valeur est alors à sa place parmi les valeurs triées. Sur une liste déjà presque dans l'ordre, chaque nouvelle valeur ne bouge que d'un ou deux pas : le tri par insertion y est donc très rapide. Sur [5, 1, 4, 2, 8], il fait 7 comparaisons et 4 échanges.

Compter les échanges : les inversions

Il existe un moyen astucieux de prévoir combien d'échanges demandent le tri à bulles et le tri par insertion. Compte les inversions : les paires de valeurs qui sont dans le mauvais ordre l'une par rapport à l'autre. Dans [5, 1, 4, 2, 8], les inversions sont (5, 1), (5, 4), (5, 2) et (4, 2), quatre en tout. Chaque échange de deux voisins mal rangés corrige exactement une inversion et n'en crée aucune : les deux méthodes font donc exactement 4 échanges. Une liste inversée de n valeurs a toutes ses paires inversées, soit n(n − 1)/2 inversions, ce qui est le pire cas.

Chaque case donne comparaisons / échanges. La liste d'exemple est [5, 1, 4, 2, 8]. Le tri à bulles est ici la version qui s'arrête après un passage sans échange.

Les trois méthodes ont la même faiblesse. Dans le pire cas, chacune compare à peu près toutes les paires de valeurs, soit environ n²/2 comparaisons. Double la liste et le travail est multiplié par quatre. Une liste dix fois plus longue demande cent fois plus de travail. Pour quelques dizaines de valeurs, cela ne compte guère ; pour un million, c'est sans espoir, et l'unité suivante montre comment faire bien mieux.