Tri par insertion en double sens.

Pour diminuer le nombre de déplacements d'éléments, le vecteur à trier est considéré comme cyclique (sa fin rejoint son début) et on n'opère les déplacements que sur des moitiés de vecteur trié. Pour ce faire, on compare l'élément à insérer à l'élément qui se trouve au milieu de la séquence triée.
Si il est plus grand, on le place dans la partie droite sinon on le place dans la partie gauche.
Si on le place dans la partie gauche, on conserve l'élément à gauche du plus petit des éléments triés, pour le placer à l'étape suivante et on décale vers la gauche les éléments triés pour insérer l'élément.
Si on le place dans la partie droite, on décale vers la droite les éléments triés, en commençant par le plus grand des triés, pour insérer l'élément à placer.

Exemple:
Soit à trier:

1 2 3 4 5 6
2 0 4 1 3 9

La partie déjà triée est écrite en rouge. 0 est inférieur à 2 et doit donc être placé dans la partie gauche. Il se place donc à gauche du 1er élément, à savoir en dernière position puisque le vecteur est considéré comme cyclique.
1 2 3 4 5 6
2 0 4 1 3 0

et on garde le 9 qui a été écrasé et doit donc être placé à cette étape. Comme 9 est supérieur à l'élément milieu (entre 0 et 2), il doit être placé dans la partie droite. Il est supérieur à 2 et donc aucun déplacement n'est nécessaire avant de le placer.
1 2 3 4 5 6
2 9 4 1 3 0

Il faut maintenant placer l'élément suivant, à savoir 4. L'élément qui se trouve au milieu de la partie triée est 2 et il est inférieur à l'élément à placer. Il faut donc insérer le 4 dans la partie droite. On recule le 9 et on insère le 4.
1 2 3 4 5 6
2 4 9 1 3 0

Il faut placer l'élément suivant, à savoir le 1. Il est plus petit que l'élément qui est au milieu de la partie triée. Il faut donc l'insérer dans la partie gauche. On conserve l'élément à gauche du plus petit des triés, à savoir 3. On déplace le 0 vers la gauche et on place le 1. Nous conservons le 3 qui doit être placé à l'étape suivante.
1 2 3 4 5 6
2 4 9 1 0 1

Comme 3 est plus grand que l'élément qui se trouve au milieu de la partie triée, on doit le placer dans la partie droite. On déplace, vers la droite; le 9, le 4 et on place le 3.
1 2 3 4 5 6
2 3 4 9 0 1

Le vecteur est trié mais il faut opérer plusieurs décalages pour amener le plus petit élément en première position:
1 2 3 4 5 6
1 2 3 4 9 0

et après le deuxième décalage:
1 2 3 4 5 6
0 1 2 3 4 9

Page précédente.

Page d'accueil.