date: 2023-10-16
Type: Cours
Projet: Blindcode
Cours: Algorithmie

Tri par Insertion

Header :

Le tri par insertion est un autre algorithme de tri simple et efficace pour trier des éléments dans un tableau. Dans ce chapitre, nous explorerons le fonctionnement du tri par insertion et analyserons sa complexité.

Body

1 .Principe de Base

Le tri par insertion fonctionne en construisant un tableau trié à partir des éléments du tableau d'origine, un élément à la fois. L'algorithme commence par considérer le premier élément du tableau comme étant déjà trié. Ensuite, il parcourt le reste du tableau, prenant chaque élément non trié et le plaçant à sa position correcte parmi les éléments déjà triés.

Voici un exemple de code en pseudo-code illustrant le tri par insertion :

FONCTION triInsertion(tableau : TABLEAU) : TABLEAU
    n <- LONGUEUR(tableau)
    POUR i DE 1 À n-1 FAIRE
        élémentCourant <- tableau[i]
        j : ENTIER <- i - 1
        TANT QUE j >= 0 ET tableau[j] > élémentCourant FAIRE
            tableau[j + 1] <- tableau[j]
            j <- j - 1
        FIN TANT QUE
        tableau[j + 1] <- élémentCourant
    FIN POUR
    RETOURNER tableau
FIN FONCTION

2 Complexité

La complexité temporelle du tri par insertion dépend du degré de désordre initial dans le tableau. Dans le meilleur des cas, lorsque le tableau est déjà trié, la complexité est linéaire, soit O(n), car aucun échange n'est nécessaire. Dans le pire des cas, lorsque le tableau est trié dans l'ordre inverse, la complexité est quadratique, soit O(n^2). En moyenne, le tri par insertion a une complexité de l'ordre de O(n^2).

La complexité spatiale est généralement O(1), car l'algorithme effectue des échanges en place, sans nécessiter de mémoire supplémentaire en fonction de la taille du tableau.

3 Avantages et Limitations

Le tri par insertion est efficace pour trier de petits tableaux ou des tableaux presque triés. Il est également stable, ce qui signifie que l'ordre relatif des éléments égaux est préservé. Cependant, pour de grands tableaux désordonnés, il peut être moins performant que d'autres algorithmes de tri plus rapides, tels que le tri rapide (QuickSort) ou le tri fusion (MergeSort).

Le tri par insertion est utile dans des situations où le tableau est déjà partiellement trié, car il peut nécessiter moins de comparaisons et d'échanges que d'autres algorithmes. Il est également utilisé comme étape intermédiaire dans d'autres algorithmes de tri.