20. Comparaison Pratique des Tris O(N²)
Bien que le Bubble Sort, le Selection Sort et l'Insertion Sort partagent tous la complexité temporelle O(N²) dans le pire des cas, leurs caractéristiques de performance diffèrent en pratique.
| Algorithme | Pire Cas (Temps) | Meilleur Cas (Temps) | Échanges/Décalages | Stabilité |
|---|---|---|---|---|
| Bubble Sort | O(N²) | O(N) | Beaucoup d'échanges/décalages | Stable |
| Selection Sort | O(N²) | O(N²) | Minimum d'échanges | Unstable |
| Insertion Sort | O(N²) | O(N) | Beaucoup de décalages, peu d'échanges | Stable |
- Stabilité : Un tri est stable s'il préserve l'ordre relatif des éléments égaux.
- Quand utiliser l'Insertion Sort : C'est le plus pratique des tris O(N²) car sa performance O(N) dans le meilleur des cas le rend très rapide pour les tableaux qui sont déjà majoritairement triés.
- Quand NE PAS utiliser : Pour les grands ensembles de données complètement non triés, nous devons passer à des algorithmes plus avancés en O(N log N).