Table des matières
1 – Le tri par insertion
1.1 – Présentation : animation et principe
Le tri par insertion est le mode de tri « naturel ».
Animation du tri par insertion
(Cliquez pour visionner la ressource en ligne)
Son principe est le suivant :
Comparer la valeur de l’élément d’index 1 du tableau avec la valeur de l’élément d’index 0 :
si la valeur de l’élément d’index 1 du tableau est inférieure à la valeur de l’élément d’index 0, alors permuter ces deux éléments.
Comparer la valeur de l’élément d’index 2 du tableau avec la valeur de l’élément d’index 1 :
si la valeur de l’élément d’index 2 du tableau est inférieure à la valeur de l’élément d’index 1, alors :
- permuter ces deux éléments ;
- puis comparer la valeur de l’élément d’index 1 du tableau avec la valeur de l’élément d’index 0 :
--- si la valeur de l’élément d’index 1 du tableau est inférieure à la valeur de l’élément d’index 0, alors permuter ces deux éléments.
Comparer la valeur de l’élément d’index 3 du tableau avec la valeur de l’élément d’index 2 :
- si la valeur de l’élément d’index 3 du tableau est inférieure à la valeur de l’élément d’index 2, alors
--- permuter ces deux éléments.
--- puis comparer la valeur de l’élément d’index 2 du tableau avec la valeur de l’élément d’index 1 :
----- si la valeur de l’élément d’index 2 du tableau est inférieure à la valeur de l’élément d’index 1, alors :
-------- permuter ces deux éléments.
-------- Puis comparer la valeur de l’élément d’index 1 du tableau avec la valeur de l’élément d’index 0 :
----------- si la valeur de l’élément d’index 1 du tableau est inférieure à la valeur de l’élément d’index 0, alors permuter ces deux éléments.
Et ainsi de suite jusqu'au dernier élément du tableauAlgorithme
Algorithme de tri par insertion
soit T un tableau de valeurs à trier
DEBUT
PARCOURIR le tableau à partir du deuxième élément jusqu'au dernier.
A chaque étape du parcours :
TANT QUE l'élément au niveau duquel on est rendu dans le parcours est
inférieur à celui qui le précède ET TANT QU'on n'a pas atteint le
premier élément du tableau, ALORS :
PERMUTER ces deux éléments
FIN TANT QUE
FINDéroulé du tri par insertion sur un exemple.
1.2 – Exercices
Exercice – Simuler un tri par insertion
Simuler le tri par insertion du tableau suivant : tableau = [‘a8Z’, ‘A2K’, ‘a8K’, ‘b2Z’, ‘B2K’].
Indication : le tri de chaînes de caractères se fait à partir d’une comparaison des valeurs d’encodage (ASCII) des caractères occupant le même rang.
Ainsi ‘AA’ est ‘inférieur à’ ‘AD’. Mais ‘Aa’ est ‘supérieur à ‘AB’.
‘A5’ est ‘inférieur à’ ‘A9’. Mais ‘a1’ est ‘supérieur à’ ‘W9’.
Compléter le tableau figurant sur la Fiche-Réponse.
Exercice – Programmer en langage Python une fonction de tri par insertion
Article sous licence 
<< Cliquez pour plus d’informations <<
<< Cliquez pour plus d’informations <<2 – Le tri par sélection.
Algorithme
Algorithme de tri par sélection
Soit T un tableau de données à trier
DÉBUT
PARCOURIR le tableau à partir du deuxième élément jusqu'au dernier.
A chaque étape du parcours :
CHERCHER la plus petite valeur du tableau comprise entre l'élément
de rang n et le dernier élément du tableau ;
PERMUTER cette valeur avec celle de rang n-1.
FIN de PARCOURIR
FINDéroulé du tri par sélection sur un exemple
Article sous licence << Cliquez pour plus d’informations <<
<< Cliquez pour plus d’informations <<