C18.3 : Tri par insertion

L'algorithme de tri par insertion est un algorithme classique qui permettent de trier une liste.

Principe

Dans cet algorithme, il s'agit de prendre les valeurs de la liste les unes après les autres et de les insérer de façon à ce qu'elles forment une portion triée de liste.

Lien : Visualisation du principe du tri par insertion

Algorithme

🖊️ Repérer les actions qui sont répétées.

🖥️ Proposer une fonction qui prend une liste en paramètre et modifie cette liste pour qu'à la fin de l'exécution de la fonction la liste soit triée par ordre croissant.

🖥️ Compléter avec le programme principal qui permet de tester la fonction avec une liste de 20 nombres entiers choisis aléatoirement entre 0 et 99.

Analyse de l'algorithme

Terminaison de l'algorithme

🖊️ Démontrer la terminaison de l'algorithme.

Correction de l'algorithme

🖊️ Proposer un invariant pour chacune des deux boucles.

Coût

🖊️ Pour quelle configuration de liste l'algorithme fait-il le moins de comparaison ? Dans ce cas combien en fait-il ?

Afficher la correction

L'algorithme fait le moins de comparaison lorsque la boucle est déjà triée.

Si on note n la longueur de la liste à trier, dans dans ce cas il fait n-1 comparaisons.

Dans ce cas, le coût de l'algorithme est proportionnel à n, on dit que le coût est linéaire.

🖊️ Pour quelle configuration de liste l'algorithme fait-il le plus de comparaison ? Dans ce cas, combien en fait-il ?

Afficher la correction

L'algorithme fait le plus de boucle lorsque la liste est totalement inversée par rapport à l'ordre souhaité.

Si on note n la longueur de la liste à trier, dans ce cas il fait 1 + 2 + 3 + ... + (n-1) = (n-1)×n/2.

Remarque : 1 + 2 + 3 + ... + k = k×(k+1)/2

Dans ce cas, le coût de l'algorithme est proportionnel à n², on dit que le coût est quadratique.

Pour aller plus loin

Lien : Algorithmes de tri

Lien : Algorithmes de tri animés