Tri par insertion linéaire.
Soit A le vecteur dont les éléments sont numérotés de 1 à N.
Nous supposons que les éléments numérotés de 1 à k sont déjà triés.
Le principe consiste en le placement de l'élément suivant, à savoir celui de
position k+1, à sa position parmi les k premiers. Cela se fait en décalant
tous les éléments, à partir du dernier élément trié, d'une position vers la
droite jusqu'à l'élément inférieur à celui à insérer et de placer ensuite
l'élément qui était en position k+1 dans le trou ainsi créé.
Exemple:
Au départ, on considére que la partie triée contient le seul premier élément
qui vaut 5 et on désire placer l'élément suivant, à savoir 4.
On déplace le 5 vers la droite (puisque plus grand que 4) pour placer le 4 à
sa place.
Nous avons donc les 2 premiers éléments qui sont dans le bon ordre. Il faut
placer maintenant le 3ème élément, à savoir 2. On déplace le 5 et le 4 (qui
sont plus grands que 2) vers la droite pour placer le 2.
Nous avons donc les 3 premiers éléments qui sont dans le bon ordre. Il faut
placer maintenant le 4ème élément, à savoir 3. On déplace le 5 et le 4 (qui
sont plus grands que 3) vers la droite pour placer le 3.
Nous avons donc les 4 premiers éléments qui sont dans le bon ordre. Il faut
placer maintenant le 5ème élément, à savoir 7. On ne déplace aucun élément
puisque 7 est plus grand que le 4ème élément, à savoir 5.
Nous avons donc les 5 premiers éléments qui sont dans le bon ordre. Il faut
placer maintenant le 6ème élément, à savoir 0. On déplace 7, 5, 4, 3, 2
(qui sont plus grands que 0) vers la droite pour placer le 0.
Note: Lors du placement du k+1 éme élément, il faut en moyenne k/2 comparaisons
pour trouver la place de l'élément dans la séquence déjà triée. Il faudra donc:
(1+2+3+...+N)/2=[(1+N)/2*N]/2 comparaisons. La méthode décrite ci-dessous
permet de réduire ce nombre à N*log N où log N est le logarithme en base 2.
Page précédente.
Page d'accueil.