Le tri insertion

Un exemple de tri insertion

Le tri par insertion est une technique de tri fondamentale en informatique, très efficace pour les petites listes et particulièrement performante pour les listes déjà partiellement triées. Sa simplicité d'implémentation et son efficacité dans certains cas particuliers le rendent incontournable dans l'étude des algorithmes de tri.

Principe du Tri par Insertion

Le tri par insertion construit la sortie triée un élément à la fois. Il prend chaque élément de la liste et l'insère à sa position correcte dans une sous-liste déjà triée. Au début, cette sous-liste triée contient uniquement le premier élément de la liste. Ensuite, l'algorithme avance dans la liste, prenant un élément à la fois et l'insérant à sa place correcte dans la partie déjà triée, jusqu'à ce que tous les éléments soient correctement positionnés.

Implémentation en Python

def tri_par_insertion(arr):
    # Parcourir de 1 à la taille du tableau
    for i in range(1, len(arr)):
        cle = arr[i]
        j = i-1
        # Déplacer les éléments de arr[0..i-1], qui sont plus grands que la clé, à une position en avant de leur position actuelle
        while j >= 0 and cle < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = cle

Preuve de la Correction

Pour prouver que le tri par insertion trie correctement une liste, on utilise l'invariant de boucle suivant : au début de chaque itération, la sous-liste arr[0..i-1] est déjà triée. Cet invariant est maintenu à chaque itération car l'algorithme insère arr[i] à sa position appropriée dans arr[0..i-1], assurant que arr[0..i] est triée. À la fin du tri, quand i a parcouru toute la liste, cela signifie que la liste entière est triée.

Preuve de Terminaison

La terminaison de l'algorithme est assurée par le fait que la boucle for avance systématiquement le pointeur i de 1, allant de 1 à \(n-1\) inclus, où \(n\) est le nombre d'éléments dans le tableau. De plus, la boucle interne while se termine car elle décrémente le pointeur \(j\) tant que la condition est vraie et s'arrête lorsque \(j\) est inférieur à 0 ou que l'élément à insérer est plus grand que arr[j].

Complexité

Le tri par insertion a une complexité temporelle moyenne et dans le pire des cas de \(O(n^2)\), où \(n\) est le nombre d'éléments dans le tableau. Cependant, dans le meilleur cas, lorsque le tableau est déjà trié, sa complexité est linéaire, soit \(O(n)\). Sa complexité en espace est \(O(1)\), car il nécessite un espace de stockage supplémentaire constant.