Algorithmique intermédiaire : analyse d'algorithmes, structures de données

Thème 7: tris

• pour chacun des 4 tris présentés (tri par insertion, tri par sélection, tri rapide, tri fusion), il faut savoir:
  • expliquer le fonctionnement de l'algorithme
  • savoir exécuter l'algorithme pas-à-pas sur un exemple
  • réécrire l'algorithme, y compris les fonctions auxiliaires utilisées
  • complexité: savoir la recalculer (pour tri par insertion et tri par sélection) ou la connaître "par coeur" (pour tri rapide et tri fusion) (les trois premiers sont en O(n^2) et le tru fusion est en O(n. log n)
• Remarque: un soin tout particulier doit être apporté à la compréhension du tri par insertion et du tri par sélection