Tri par insertion : Implémentation et complexité

1. Le Principe du Tri par Insertion

Imaginez que vous triez un jeu de cartes que vous avez en main. Vous prenez les cartes une par une et vous insérez chacune à sa bonne place parmi celles que vous avez déjà triées. C'est exactement le principe du tri par insertion.

L'algorithme parcourt un tableau d'éléments. À chaque étape, il prend l'élément courant et l'insère à la position correcte dans la partie du tableau qui est déjà triée, située à sa gauche.

Pour vous familiariser avec ce mécanisme, je vous propose de regarder une courte séquence vidéo qui explique le principe et déroule un exemple.

L'image suivante décompose également le processus complet sur un exemple, passe par passe.

L'opération clé est donc "l'insertion" de l'élément à sa bonne place, qui se fait par une série de décalages (ou d'échanges) vers la droite des éléments qui lui sont supérieurs.

2. Analyse de Complexité

Maintenant que le principe est clair, nous devons analyser sa performance. Une des forces de cet algorithme, et une subtilité importante à maîtriser, est que sa complexité dépend fortement de l'état initial du tableau.

Pour une analyse rigoureuse, je vous propose d'étudier un document de préparation à l'Agrégation qui détaille parfaitement les cas qui nous intéressent.

Synthétisons et formalisons cette analyse. Nous comptons le nombre de comparaisons comme opération élémentaire.

Pire des cas

Le pire cas se produit lorsque le tableau est trié en ordre décroissant.
À chaque itération i de la boucle externe (pour les éléments de l'indice 1 à n-1), l'élément A[i] est le plus petit de la sous-liste A[0...i]. Il doit donc être comparé à tous les i éléments qui le précèdent avant d'être placé en position 0.

• Pour i = 1, on fait 1 comparaison.
• Pour i = 2, on fait 2 comparaisons.
• ...
• Pour i = n-1, on fait n-1 comparaisons.

Le nombre total de comparaisons dans le pire cas, $C_{pire}(n)$, est donc la somme des i premiers entiers :
$C_{pire}(n)={\sum }_{i=1}^{n-1}i=\frac{(n-1)n}{2}$
Cette somme est de l'ordre de $n^2$. La complexité dans le pire des cas est donc $\Theta (n^2)$.

Meilleur des cas

Le meilleur cas se produit lorsque le tableau est déjà trié.
À chaque itération i de la boucle externe, l'élément A[i] est déjà plus grand que l'élément qui le précède, A[i-1]. La boucle interne s'exécute donc une seule fois (une seule comparaison) et s'arrête immédiatement.

• Pour chaque i de 1 à n-1, on effectue 1 seule comparaison.

Le nombre total de comparaisons dans le meilleur des cas, $C_{meilleur}(n)$, est :
$C_{meilleur}(n)={\sum }_{i=1}^{n-1}1=n-1$
La complexité dans le meilleur des cas est donc $\Theta (n)$.

Cette propriété (on dit que l'algorithme est adaptatif) est très importante : le tri par insertion est très efficace pour des tableaux qui sont déjà "presque" triés.

La vidéo suivante approfondit cette analyse et discute des coûts respectifs des comparaisons et des échanges (swaps).

3. Implémentation en Python

Passons maintenant à la pratique. L'algorithme s'implémente de manière concise avec deux boucles imbriquées.

Voici le pseudo-code pour une version itérative et en place (c'est-à-dire qui ne nécessite pas de tableau auxiliaire, la complexité spatiale est en $O(1)$) :

fonction TriInsertion(tableau A):
  pour i de 1 à longueur(A) - 1:
    cle = A[i]
    j = i - 1
    pendant que j >= 0 et A[j] > cle:
      A[j + 1] = A[j]
      j = j - 1
    A[j + 1] = cle

Et voici son implémentation en Python :

def insertion_sort(arr):
    """
    Trie un tableau en utilisant l'algorithme du tri par insertion.
    """



    # On parcourt le tableau à partir du deuxième élément (indice 1)
    for i in range(1, len(arr)):
        key = arr[i]  # L'élément à insérer
        j = i - 1     # L'indice du dernier élément de la partie triée




        # On décale les éléments de la partie triée qui sont plus grands que la clé
        # vers la droite pour créer de l'espace.
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        



        # On insère la clé à sa position correcte
        arr[j + 1] = key




# Exemple d'utilisation
my_array = [23, 1, 10, 5, 2]
insertion_sort(my_array)
print("Tableau trié:", my_array)




# Exemple du meilleur cas
sorted_array = [1, 2, 5, 10, 23]
insertion_sort(sorted_array)
print("Meilleur cas:", sorted_array)




# Exemple du pire cas
reverse_sorted_array = [23, 10, 5, 2, 1]
insertion_sort(reverse_sorted_array)
print("Pire cas:", reverse_sorted_array)

Exercice pratique

Prenez le temps de réécrire cette fonction insertion_sort par vous-même, sans copier-coller. Assurez-vous de bien comprendre le rôle de chaque variable, en particulier l'invariant de boucle implicite : au début de chaque itération i de la boucle for, le sous-tableau arr[0...i-1] est trié.

Conclusion

Le tri par insertion est notre première incursion dans une famille d'algorithmes fondamentaux. Sa simplicité en fait un excellent point de départ.

À retenir :

• Principe : Insérer itérativement chaque élément à sa place dans une sous-liste déjà triée.
• Complexité spatiale : C'est un tri en place, sa complexité spatiale est de $O(1)$.
• Complexité temporelle (pire cas) : $\Theta (n^2)$, lorsque les données sont triées en ordre inverse.
• Complexité temporelle (meilleur cas) : $\Theta (n)$, lorsque les données sont déjà triées. C'est un algorithme adaptatif.
• Stabilité : Le tri par insertion est un algorithme stable, ce qui signifie qu'il préserve l'ordre relatif des éléments de valeur égale.

Bien que sa complexité quadratique le rende inefficace pour de grands ensembles de données aléatoires, sa performance en cas de données presque triées et sa faible surcharge le rendent utile dans certains contextes, et il est souvent utilisé comme composant dans des algorithmes de tri plus complexes.

Dans la prochaine leçon, nous étudierons un algorithme basé sur une approche radicalement différente, "diviser pour régner" : le tri fusion. Nous verrons comment il atteint une complexité de $O(n\log n)$ dans tous les cas, au prix d'une complexité spatiale plus élevée.