Recherche…
Paramètres
| Paramètre | La description |
|---|---|
| La stabilité | Un algorithme de tri est stable s'il conserve l'ordre relatif des éléments égaux après le tri. |
| En place | Un algorithme de tri est en place s'il trie en utilisant uniquement la mémoire auxiliaire O(1) (sans compter le tableau à trier). |
| Meilleure complexité de cas | Un algorithme de tri a la meilleure complexité temporelle en O(T(n)) si son temps d'exécution est au moins T(n) pour toutes les entrées possibles. |
| Complexité moyenne des cas | Un algorithme de tri a une complexité moyenne en temps de cas de O(T(n)) si son temps d'exécution, moyenné sur toutes les entrées possibles , est T(n) . |
| La pire complexité | Un algorithme de tri a la complexité temporelle la plus défavorable de O(T(n)) si son temps d'exécution est au maximum T(n) . |
Stabilité en tri
La stabilité dans le tri signifie si un algorithme de tri maintient l'ordre relatif des clés égales de l'entrée d'origine dans la sortie du résultat.
Ainsi, un algorithme de tri est dit stable si deux objets avec des clés égales apparaissent dans le même ordre dans la sortie triée, car ils apparaissent dans le tableau non trié en entrée.
Considérons une liste de paires:
(1, 2) (9, 7) (3, 4) (8, 6) (9, 3)
Maintenant, nous allons trier la liste en utilisant le premier élément de chaque paire.
Un tri stable de cette liste affichera la liste ci-dessous:
(1, 2) (3, 4) (8, 6) (9, 7) (9, 3)
Car (9, 3) apparaît également après (9, 7) dans la liste originale.
Un tri instable affichera la liste ci-dessous:
(1, 2) (3, 4) (8, 6) (9, 3) (9, 7)
Le tri instable peut générer le même résultat que le tri stable, mais pas toujours.
Sortes d'écuries bien connues:
Sortes instables bien connues: