Tri stable
Un article de Wikipédia, l'encyclopédie libre.
Un tri stable est un algorithme de tri qui conserve l'ordre initial de deux éléments lorsque ceux-ci sont considérés comme "égaux" par la relation d'ordre choisie.
[modifier] Exemple
Soient tri1 un algorithme de tri stable et tri2 un algorithme de tri instable[1].
Trions la liste lst = [ [1, b], [2, b], [3, a] ] sur le 2e paramètre de chaque élément.
On obtiendra forcément
- tri1(lst) = [ [3, a], [1, b], [2, b] ]
mais il est possible que l'on obtienne
- tri2(lst) = [ [3, a], [2, b], [1, b] ]
- ↑ c'est-à-dire, qui ne conserve pas forcément l'ordre des éléments "égaux"
