|
|
|
|
|
|
|
Tri
par insertion
Le tri par insertion est le tri le plus efficace sur des listes de
petite taille. C'est pourquoi il est utilisé par d'autres méthodes
comme le Tri rapide (ou quicksort).
Le principe de ce tri est très simple: c'est le tri que toute
personne normale utilise quand elle a des dossiers (ou n'importe
quoi d'autre) à classer. On prend un dossier et on le met à sa
place parmi les dossiers déjà triés. Puis on recommence avec le
dossier suivant.
Pour procéder à un tri par insertion, il suffit de parcourir une
liste : on prend les éléments dans l'ordre. Ensuite, on les
compare avec les éléments précédents jusqu'à trouver la place de
l'élément qu'on considère. Il ne reste plus qu'à décaler les
éléments du tableau pour insérer l'élément considéré à sa place
dans la partie déjà triée.
Propriétés
Dans le cas du tri par insertion sur un tableau comme implémenté
plus bas (implémentation la plus courante), les propriétés
suivantes sont vérifiées:
Le nombre de comparaisons nécessaires est de l'ordre de N²/2.
Le nombre moyen d'échanges est de l'ordre de N²/4.
Si une liste chaînée est utilisée, il n'y a plus d'échanges à
faire (les insertions se font en temps constant), mais le nombre
de comparaisons pour trouver l'emplacement où insérer reste de
l'ordre de N²/4.
A contrario, avec un tableau il est possible de faire un nombre de
comparaisons de l'ordre de N.ln(N) en utilisant une recherche par
dichotomie pour trouver l'emplacement où insérer l'élément.
Néanmoins le nombre moyen d'échanges ne sera pas modifié, et
l'algorithme reste peu efficace sur les grands tableaux par
rapport au tri rapide.
Dans le cas d'une liste presque triée, où seules quelques
comparaisons et échanges sont nécessaires par élément,
l'implémentation la plus courante du tri par insertion est souvent
la meilleure méthode de tri.
Le tri par insertion est un tri stable (conservant l'ordre
d'apparition des éléments égaux) et un tri sur place (les éléments
sont directement triés dans la structure).
pascal:
|
|
|
|
|
|
|
