Introduction aux algorithmes de tri et leur complexité

📋 Plan du Cours

1. Tri par sélection & complexité
2. Tri par insertion & décalages
3. Algorithmes de tri & principes
4. Complexité quadratique & cas pire
5. Fonctionnement & schémas explicatifs
6. Implémentation & vérification
7. Comparaison & impact sur performances
8. Étude du pire cas & décalages

📖 1. Tri par sélection & complexité

🔑 Notions clés & Définitions

• Tri par sélection : Algorithme de tri qui consiste à parcourir le tableau pour trouver le minimum, puis à échanger cet élément avec celui en début de sous-tableau non trié. Répète jusqu'à ce que tout le tableau soit trié.
• Complexité en temps : Mesure du nombre d'opérations effectuées par un algorithme en fonction de la taille de l'entrée, souvent exprimée en notation Big O.
• Pire cas : Situation où l'algorithme nécessite le plus de ressources (comparaisons, décalages) pour trier le tableau.
• Décalage : Opération consistant à déplacer un élément pour faire de la place à un nouvel élément lors du tri par insertion.
• Complexité quadratique (O(n²)) : Classe de complexité où le temps d'exécution croît proportionnellement au carré de la taille du tableau.

📝 Points essentiels