Tri par insertion

Adaptatif, stable, O(n) meilleur cas

← Retour au cours Tri

Algorithme complet

stable

Insérer l'élément courant dans la partie gauche déjà triée.

element = tableau[indice]
Élément à placer
while tableau[j-1] > element
Décalage (strict >)
tableau[position] = element
Insertion finale
tri_insertion.py 
def tri_insertion(tableau):
    nb_elements = len(tableau)
    for indice in range(1, nb_elements):
        element_a_inserer = tableau[indice]
        position = indice
        while position > 0 and tableau[position - 1] > element_a_inserer:
            tableau[position] = tableau[position - 1]
            position = position - 1
        tableau[position] = element_a_inserer

Cas limites

adaptatif

Déjà trié → O(n) ; inverse → O(n²).

Meilleur cas
O(n) : une comparaison par indice
Pire cas
O(n²)
Stable
Oui si comparaison stricte

💻 Exemples de code

Exemple d'utilisation

exemple_tri_insertion.py 
temperatures = [22, 18, 25, 19]
tri_insertion(temperatures)
print(temperatures)   # [18, 19, 22, 25]

📋 Aide-mémoire

Variant de terminaison : j décroît strictement, minoré par 0.