Tri par insertion
Un article de Wikipédia, l'encyclopédie libre.
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). Il est d'autant plus rapide que les données sont déjà triées en partie dans le bon ordre.
Le principe de ce tri est très simple: c'est le tri que toute personne utilise naturellement 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. On peut aussi faire une recherche par dichotomie sur les tableaux.
Une amélioration possible de ce tri, sensible pour les listes de plus de 15 éléments, est le tri de Shell.
Sommaire |
[modifier] 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.
Compter en terme d'échanges n'est pas forcément adéquat pour ce tri. En effet, on peut faire des copies successives des éléments décalés plutôt que de les échanger ce qui divise par deux le nombre d'accès aux éléments.
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 et il est difficile d'optimiser cette recherche.
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. Par contre, si les éléments sont dans l'ordre inverse au départ, il s'agit du pire des cas et il faut N*(N-1)/2 échanges.
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).
[modifier] Optimisations possibles
On peut optimiser ce tri en commençant par un élément au milieu de la liste puis en triant alternativement les éléments après et avant. On peut alors insérer le nouvel élément soit à la fin, soit au début des éléments triés, ce qui divise par deux le nombre moyen d'éléments décalés.
Contrairement à l'optimisation de Shell, cette optimisation permet de garder la stabilité du tri.
[modifier] Implémentations
Une mise en œuvre simple du tri par insertion sur un tableau de nombres réels en C :
#define MAX 100
void insertion(int t[MAX]) {
/* Spécifications externes : Tri du tableau t par insertion séquentielle */
int i,p,j;
double x;
for (i = 1; i < MAX; i++) {
/* stockage de la valeur en i */
x = t[i];
/* recherche du plus petit indice p inférieur à i tel que t[p] >= t[i] */
for(p = 0; t[p] < x; p++);
/* p pointe une valeur de t supérieure à celle en i */
/* décalage avant des valeurs de t entre p et i */
for (j = i-1; j >= p; j--) {
t[j+1] = t[j];
}
/* insertion de la valeur stockée à la place vacante */
t[p] = x;
}
}
Tri par insertion en Pascal en ordre croissant.
const MAX = 100;
type tab = array [1..MAX] of real;
Procedure TriInsertion(n : integer ; var t : tab);
var i, j : integer;
var z : real;
begin
for i:=2 to n do begin
z := t[i]; (* z est la valeur à insérer *)
(* dans l'endroit approprié du tableau *)
(* On décale toutes les valeurs du tableau < z *)
(* à droite pour vider une place pour z *)
j := i - 1;
while (j >= 1) and (t[j] > z) do begin
t[j + 1] := t[j];
j := j - 1;
end;
(* finalement la valeur z est insérée à son emplacement adéquat *)
t[j + 1] := z;
end;
end;
Tri par insertion récursif en utilisant des listes en OCaml.
let rec insere elem = function
[] -> [elem]
| tete::queue ->
if elem < tete
then elem::tete::queue (* on a trouvé la place de l'élément *)
else tete :: (insere elem queue) (* on continue à chercher dans la queue de la liste *)
let rec tri_insertion = function
[] -> []
| tete::queue -> insere tete (tri_insertion queue)
On remarque que le listes sont des structures de données plus simples à trier par insertion que les tableaux, parce qu'il n'y a pas besoin de "décaler les éléments".
Tri par insertion en ordre croissant en utilisant le langage Java (JDK avant la version 5.0)
[modifier] Algorithme du tri par insertion:
DEBUT
Const N=/*Valeur positive*/
Var Tab:tableau(1..N) entier
Tampon,i,k:entier
Pour i<---2 à N faire
Tampon<---Tab[i]
k<---i
Tantque(k>1 et Tab[k-1]>Tampon) faire
k<---k-1
FinTantque
Tab[k]<---Tampon
FinPour
FIN
[modifier] Tri par insertion en PHP
function insert_sort($arr){
$count = count($arr);
for($i=1; $i<$count; $i++){
$tmp = $arr[$i];
$j = $i - 1;
while($arr[$j] > $tmp){
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
$j–-;
}
}
return $arr;
}
[modifier] Tri par insertion en Python
def insertionSort(array):
j = 1
n = len(array)
while j != n:
i = j - 1
tmp = array[j]
while i > -1 and array[i] > tmp:
array[i+1] = array[i]
i = i - 1
array[i+1] = tmp
j = j + 1
