}
}
}
e. Le tri par insertion
Le tri par insertion consiste à sélectionner un élément du tableau et à l’insérer directement à la bonne position dans la
partie du tableau déjà triée. On procède en trois étapes :
q On place l’élément à trier dans une variable temporaire.
q Tant que les éléments du tableau qui précèdent l’élément à trier lui sont supérieurs, on décale ces éléments
d’une position en récupérant l’espace vide laissé par l’élément à trier.
q On insère ensuite la variable temporaire à la nouvelle position laissée vacante par le décalage.
Voici les différentes étapes pour le tableau exemple :
q Étape 1 : le deuxième élément 17 est placé dans une variable temporaire qui est comparée aux éléments qui
le précèdent. Chacun est décalé tant qu’il est supérieur à l’élément à trier.
q Étape 2 : 25 est comparé aux éléments qui le précédent et chacun est décalé jusqu’à ce que l’élément ne soit
plus supérieur au troisième.
q Étape 3 : 9 est comparé aux éléments qui le précèdent. Ici comme dans l’étape 1 on s’arrête forcément au
premier élément.
q Étape 4 : 34 est comparé aux éléments qui le précèdent. Seul 48 lui est supérieur.
L’algorithme résultant est assez simple. Seule la boucle de décalage peut être un peu plus ardue à comprendre.
Chaque élément est décalé vers la droite (ou le bas selon la représentation qu’on s’en fait) du tableau tant qu’il est
supérieur à l’élément recherche.
PROGRAMME TRINSERTION
VAR
i,mem,pos:entiers
t:tableau[1..5] d’entiers
DEBUT
Cpt←5
Pour i de 1 à Cpt faire
mem←t[i]
48
17
25
9
34
48
25
9
34
17
48
25
9
34
17 en temporaire
Décalage de 48
17 à la nouvelle position
17
48
25
9
34
17
48
9
34
17
25
48
9
34
25 en temporaire
Décalage de 48
25 à la nouvelle position
17
25
48
9
34
17
25
48
34
9
17
25
48
34
9 en temporaire
Décalage de 17, 25 et 48
9 à la nouvelle position
9
17
25
34
48
9
17
25
48
9
17
25
34
48
9 en temporaire
Décalage de 48
34 à la nouvelle position
- 5 -
© ENI Editions - All rigths reserved - Jonifar lina
112
}
}
e. Le tri par insertion
Le tri par insertion consiste à sélectionner un élément du tableau et à l’insérer directement à la bonne position dans la
partie du tableau déjà triée. On procède en trois étapes :
q On place l’élément à trier dans une variable temporaire.
q Tant que les éléments du tableau qui précèdent l’élément à trier lui sont supérieurs, on décale ces éléments
d’une position en récupérant l’espace vide laissé par l’élément à trier.
q On insère ensuite la variable temporaire à la nouvelle position laissée vacante par le décalage.
Voici les différentes étapes pour le tableau exemple :
q Étape 1 : le deuxième élément 17 est placé dans une variable temporaire qui est comparée aux éléments qui
le précèdent. Chacun est décalé tant qu’il est supérieur à l’élément à trier.
q Étape 2 : 25 est comparé aux éléments qui le précédent et chacun est décalé jusqu’à ce que l’élément ne soit
plus supérieur au troisième.
q Étape 3 : 9 est comparé aux éléments qui le précèdent. Ici comme dans l’étape 1 on s’arrête forcément au
premier élément.
q Étape 4 : 34 est comparé aux éléments qui le précèdent. Seul 48 lui est supérieur.
L’algorithme résultant est assez simple. Seule la boucle de décalage peut être un peu plus ardue à comprendre.
Chaque élément est décalé vers la droite (ou le bas selon la représentation qu’on s’en fait) du tableau tant qu’il est
supérieur à l’élément recherche.
PROGRAMME TRINSERTION
VAR
i,mem,pos:entiers
t:tableau[1..5] d’entiers
DEBUT
Cpt←5
Pour i de 1 à Cpt faire
mem←t[i]
48
17
25
9
34
48
25
9
34
17
48
25
9
34
17 en temporaire
Décalage de 48
17 à la nouvelle position
17
48
25
9
34
17
48
9
34
17
25
48
9
34
25 en temporaire
Décalage de 48
25 à la nouvelle position
17
25
48
9
34
17
25
48
34
9
17
25
48
34
9 en temporaire
Décalage de 17, 25 et 48
9 à la nouvelle position
9
17
25
34
48
9
17
25
48
9
17
25
34
48
9 en temporaire
Décalage de 48
34 à la nouvelle position
- 5 -
© ENI Editions - All rigths reserved - Jonifar lina
112