stabilité
Définition
Propriété présentée par un algorithme de tri qui respect l'ordre initial des données soumises au tri et qui ne nécessitent pas réarrangement selon la clef de tri. Exemple:
| Clef | Autre donnée |
|---|---|
| 2 | deuxième choix |
| 3 | troisième choix |
| 1 | premier choix |
| 2 | autre deuxième choix |
Une fois les données triées par un tri stable sur la colonne "clef", le résultat DOIT être
| Clef | Autre donnée |
|---|---|
| 1 | premier choix |
| 2 | deuxième choix |
| 2 | autre deuxième choix |
| 3 | troisième choix |
Alors qu'un algorithme de tri instable sur la même clef pourrait donner indifféremment le résultat précédent ou le suivant:
| Clef | Autre donnée |
|---|---|
| 1 | premier choix |
| 2 | autre deuxième choix |
| 2 | deuxième choix |
| 3 | troisième choix |
En particulier, tout algorithme de tri intégral est instable pour toute clef autre qu'une clef composée de l'ensemble des colonnes triées.
