Stabilité des algorithmes de tri
On dit qu'un algorithme de tri est stable s'il ne modifie pas l'ordre initial des clés identiques.
Par exemple, imaginez que vous vouliez trier la collection de bouteilles ci-dessous par ordre de volume (le volume est indiqué sous la bouteille) :
Si vous obtenez ceci, alors votre tri n'était pas stable :
En effet, la bouteille noire de volume 1 se trouve maintenant avant la bouteille bleue de même volume alors qu'elle devrait être après. Il en est de même pour les deux bouteilles de volume 4 qui sont inversées par rapport à l'ordre initial.
Avec un tri stable, on aurait obtenu :
L'intérêt d'un tri stable est qu'on peut appliquer ce tri successivement, avec des critères différents. Imaginez, par exemple, que dans le cadre d'une campagne de prévention, vous vouliez trier une liste de personnes en fonction de la catégorie d'âge. Vous obtenez une liste avec les personnes les plus âgées en premier. Si maintenant, vous voulez re-trier cette liste en fonction du poids, par exemple, vous aurez, si l'algorithme de tri est stable, les personnes les plus lourdes en premier et, pour les personnes de même poids, celles qui sont les plus âgées en premier. Ce qu'un algorithme non-stable ne garantirait pas.
L'animation ci-dessous vérifie, de manière empirique, la stabilité de plusieurs algorithmes de tri : tri par sélection, tri par insertion, tri à bulle, tri shaker, tri à peigne, tri Gnome, tri Shell, tri fusion, tri Oyelami, tri rapide,.
Elle génére un tableau de 400 éléments, comportant des doublons, triplons et même des quadruplons. Le chiffre du haut indique le "poids" de l'élément, c'est sur ce poids que le tableau sera trié. Le chiffre du bas indique la position d'origine dans le tableau.
Utilisez ensuite le bouton "Trier" pour voir le résultat.