Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

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

1. Le nombre de comparaisons nécessaires est de l'ordre de N²/4.
2. Le nombre moyen d'échanges est de l'ordre de N²/2.