01 — Tri par sélection et tri par insertion

Ce que tu vas apprendre

• Le tri par sélection : trouver le minimum, le placer, recommencer
• Le tri par insertion : insérer chaque élément à sa place
• Pourquoi les deux sont en O(n²) mais ne se valent pas
• Pourquoi l'insertion est le tri de choix sur les petits tableaux

Prérequis

• 00 — Introduction

Quand on demande à quelqu'un qui n'a jamais étudié le tri de ranger un paquet de cartes, il réinvente presque toujours l'un de ces deux algorithmes. Le tri par sélection et le tri par insertion sont les plus intuitifs. Ils sont aussi les plus lents des tris utiles, tous deux en O(n²). Mais leur étude pose les bases, et l'insertion reste utilisée en pratique, à l'intérieur des tris rapides modernes.

Le tri par sélection

Le principe tient en une phrase : trouver le plus petit élément, le mettre en première position, puis recommencer sur le reste. À chaque tour, on sélectionne le minimum de la partie non triée et on l'échange avec le premier élément non trié.

typescriptfunction triSelection(arr: number[]): number[] {
  for (let i = 0; i < arr.length - 1; i++) {
    let indexMin = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[indexMin]) indexMin = j;
    }
    if (indexMin !== i) {
      [arr[i], arr[indexMin]] = [arr[indexMin], arr[i]]; // échange
    }
  }
  return arr;
}

Deux boucles imbriquées : la première parcourt les positions, la seconde cherche le minimum dans le reste. C'est l'image type du O(n²) vue dans la série Complexité. Et le coût ne change pas selon les données : même un tableau déjà trié subit toutes les comparaisons. Le tri par sélection est donc en O(n²) dans tous les cas, meilleur comme pire.

Son seul atout : il fait peu d'échanges, au plus n - 1. Si déplacer un élément coûte très cher (de gros objets), ça peut compter. Sinon, il n'a aucun intérêt pratique. Notons qu'il est instable : l'échange peut faire passer un élément égal devant un autre.

Le tri par insertion

Le principe est celui du joueur de cartes qui range sa main : il prend les cartes une par une et insère chacune à sa place parmi celles déjà triées. On parcourt le tableau de gauche à droite, et pour chaque élément, on le décale vers la gauche tant qu'il est plus petit que son voisin.

pythondef tri_insertion(arr: list[int]) -> list[int]:
    for i in range(1, len(arr)):
        courant = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > courant:
            arr[j + 1] = arr[j]   # on décale vers la droite
            j -= 1
        arr[j + 1] = courant       # on insère à la bonne place
    return arr

À première vue, c'est encore deux boucles, donc O(n²). C'est vrai dans le pire cas (un tableau trié à l'envers : chaque élément doit remonter tout le début). Mais le cas le plus favorable est très différent.

Pourquoi l'insertion bat la sélection

La différence se joue sur le meilleur cas. Si le tableau est déjà trié, la boucle interne du tri par insertion ne s'exécute jamais : chaque élément est déjà à sa place, on ne décale rien. On fait une seule passe de n comparaisons. Le meilleur cas du tri par insertion est donc O(n), contre O(n²) pour la sélection.

Cette propriété rend l'insertion excellente sur les données presque triées, un cas fréquent en pratique (ajouter quelques éléments à une liste déjà ordonnée). Le tri par insertion est aussi stable : on ne déplace un élément que s'il est strictement plus petit, donc deux éléments égaux gardent leur ordre.

Le détail qui compte : l'insertion dans les vrais tris

Le tri par insertion a un avantage caché : il est très rapide sur les petits tableaux, parce qu'il a peu de surcoût (pas de récursion, pas d'allocation). Pour cette raison, les tris performants comme le tri rapide ou Timsort basculent sur un tri par insertion dès que le sous-tableau à trier devient petit, typiquement moins de 10 à 16 éléments. On le verra à l'article 07.

Autrement dit, ces deux tris « jouets » ne sont pas que pédagogiques : l'insertion est une brique des tris industriels. Mais sur de gros volumes pris isolément, ils sont à éviter. L'article suivant traite le cas le plus connu et le plus décrié de cette famille quadratique : le tri à bulles.

Sources

• Videau, M., & Eck, D. (2004). Les algorithmes de tri. Interstices. interstices.info/les-algorithmes-de-tri/
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Section 2.1 "Insertion Sort". MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 2.1 "Elementary Sorts". Addison-Wesley.