Le tri par insertion

Le tri par insertion fonctionne comme quand tu ranges des cartes à jouer dans ta main : tu prends les cartes une par une et tu insères chacune à sa bonne place parmi celles déjà triées. Contrairement au tri par sélection, ici on construit une partie triée en insérant les éléments un par un, pas en cherchant un minimum global.

Le principe : pour chaque élément à la position i (à partir de i=1), tu le retiens (la « clé »), puis tu décales vers la droite tous les éléments déjà triés qui sont plus grands que la clé, et tu places enfin la clé dans le trou laissé libre.

Schéma sur [5, 2, 4, 1, 3] :

depart  : [5, 2, 4, 1, 3]
etape 1 : [2, 5, 4, 1, 3]   (on insere 2 avant 5)
etape 2 : [2, 4, 5, 1, 3]   (on insere 4 entre 2 et 5)
etape 3 : [1, 2, 4, 5, 3]   (on insere 1 tout au debut)
etape 4 : [1, 2, 3, 4, 5]   (on insere 3 entre 2 et 4)

[ ...trie... | cle a inserer | ...pas encore vu... ]

Dans le pire cas (tableau trié à l'envers), chaque insertion décale presque tous les éléments déjà traités : c'est encore O(n²). Mais dans le meilleur cas (tableau déjà trié), chaque élément ne se compare qu'une fois avec son voisin immédiat : c'est O(n), bien plus rapide. C'est pourquoi le tri par insertion est souvent utilisé pour des petits tableaux ou des tableaux presque triés.

def tri_insertion(a):
    a = a[:]
    for i in range(1, len(a)):
        cle = a[i]
        j = i - 1
        while j >= 0 and a[j] > cle:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = cle
    return a

Piège classique : la condition j >= 0 doit être vérifiée AVANT a[j] > cle dans le while (sinon Python teste a[-1] par erreur d'ordre, ou pire dans un autre langage cela dépasse le tableau).