Algorithmes Python

Le tri par insertion (insertion sort) en Python

Dans cette leçon, vous allez implémenter le tri par insertion en insérant chaque élément à sa place dans la partie déjà triée.

  • Intermédiaire
  • 2 min de lecture
  • 1 exemple exécutable

Introduction

Le problème

Les données arrivent souvent presque triées, ou un élément à la fois : une liste de notes triée reçoit une nouvelle note. Tout retrier est du gaspillage. Le tri par insertion gère très bien ce cas, et c'est ainsi que beaucoup de gens trient des cartes à jouer à la main.

Imaginez-le ainsi

Le tri par insertion, c'est la façon de trier les cartes dans sa main. Vous prenez une carte à la fois et la faites glisser vers la gauche au-delà de chaque carte plus grande jusqu'à ce qu'elle soit à la bonne place. Les cartes à sa gauche sont toujours dans l'ordre.

Du tri de cartes au code
current = result[index]🃏 Prendre la carte suivante
result[position] > current👈 La carte de gauche est-elle plus grande ?
result[position + 1] = result[position]➡️ Faire glisser la plus grande d'une place vers la droite
result[position + 1] = current📥 Poser la carte dans le trou
La partie gauche est toujours triée ; chaque nouvel élément y est inséré.
En une phrase

Le tri par insertion construit une partie triée un élément à la fois en décalant les éléments plus grands vers la droite et en insérant l'élément courant dans le trou ; il est en O(n²) dans le pire cas mais proche de O(n) sur des données presque triées.

Points clés

  1. for index in range(1, len(result)): commence au deuxième élément ; un seul élément est déjà trié.
  2. current garde la valeur à insérer pendant que les plus grandes se déplacent.
  3. while position >= 0 and result[position] > current: décale chaque valeur plus grande d'une place vers la droite.
  4. result[position + 1] = current pose la valeur dans le trou qui a été ouvert.

Quand l’utiliser ?

  • Les listes petites ou presque triées.
  • Garder une liste triée à mesure que de nouveaux éléments arrivent.
  • L'étape finale dans des tris plus rapides, qui passent au tri par insertion pour les petits morceaux.

Quand s'en passer

  • Les grandes listes aléatoires : les décalages deviennent lents, utilisez donc sorted().
  • Insérer souvent dans une grande liste triée : bisect.insort trouve la position par recherche dichotomique.

Visualisation de Le tri par insertion (insertion sort) en Python

O(n²)

Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.

Code d’exemple

Exécuter le code →
main.py
def insertion_sort(values):
    result = values.copy()
    for index in range(1, len(result)):
        current = result[index]
        position = index - 1
        while position >= 0 and result[position] > current:
            result[position + 1] = result[position]
            position -= 1
        result[position + 1] = current
    return result

print(insertion_sort([9, 5, 1, 4, 3]))
Obtenir un bouton Run pour cet exemple

Résultat de l’exécution

[1, 3, 4, 5, 9]

Explication du code

La variable current contient la valeur à insérer. La boucle while décale d'une position vers la droite les valeurs plus grandes que current pour libérer de la place, puis current est placé à cet endroit. Dans le pire des cas, la complexité est O(n²), mais avec des données presque triées l'algorithme s'approche de O(n).

Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.

Exercices d’approfondissement

Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.

  1. Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
  2. Affichez l’état après chaque étape pour observer l’algorithme en action.
  3. Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Exécuter dans le compilateur Python →

Erreurs fréquentes

Réécrire current dans la boucle

La valeur doit être placée une seule fois, après le déplacement de toutes les valeurs plus grandes.

Problème
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    result[position] = current
    position -= 1
Correction
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    position -= 1
result[position + 1] = current

Leçon terminée ?

Marquez-la comme apprise pour suivre votre progression.

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis