Algorithmes de tri
Organiser des données selon un ordre donné facilite recherche, comparaison et exploitation.
1
Notions de base
À retenir
Un tri réordonne une suite selon un critère. Le choix dépend des données, de la mémoire et de la stabilité.
Critères de comparaison
| Critère | Idée |
|---|---|
| Complexité temporelle | Nombre d'opérations selon n |
| Complexité spatiale | Mémoire supplémentaire utilisée |
| Stabilité | Conserver l'ordre des égaux |
2
Insertion et sélection
Comparer deux tris simples
Tri par insertion
- Construit un préfixe trié progressivement.
- Bon si le tableau est presque trié.
- Stabilité généralement conservée.
Tri par sélection
- Choisit le minimum à chaque étape.
- Effectue peu d'échanges.
- Stabilité non garantie.
Idée mnémotechnique
Insertion = on glisse l'élément. Sélection = on prend le plus petit.
3
Tri fusion
Principe
- 1
Diviser le tableau en deux moitiés.
- 2
Trier récursivement chaque moitié.
- 3
Fusionner deux sous-tableaux triés.
Point clé
Le tri fusion combine division récursive et fusion linéaire.
4
Tri rapide
Principe
Idées essentielles
- Très rapide en moyenne.
- Pire cas quadratique.
5
Choisir le bon tri
Cas d'usage
Privilégier insertion
- Petites tailles.
- Données presque triées.
- Simplicité recherchée.
Privilégier fusion ou rapide
- Grandes données.
- Besoin de bonnes performances.
- Contraintes mémoire ou stabilité à vérifier.
Mini-défi
- Quel tri garde l'ordre des égaux ?
- Quel tri dépend d'un pivot ?
Conclusion
- Insertion et sélection sont simples mais quadratiques.
- Fusion est stable et en O(n \log n).