Tris et structures de données

#Révision des tris et structures de donnéesCopier le lien

Cette section sert de révision guidée. Nous reprenons les algorithmes de tri classiques en identifiant leurs domaines d’excellence : insertion, sélection ou bulles restent pertinents pour de très petites tailles ou des données presque triées, tandis que tri fusion, tri rapide et tas dominent sur de grands ensembles. Les variantes (pivot median-of-three, partition stable) sont analysées expérimentalement afin de comprendre l’impact des choix d’implémentation. Les tris par comptage ou radix sont présentés comme des alternatives puissantes lorsque les clés sont entières et bornées.

Côté structures, nous mettons en balance tableaux dynamiques et listes chaînées, discutons des différents types de tas (binaire, Fibonacci, binomial) et expliquons comment Union-Find atteint presque la constante grâce à la compression de chemin (α(n)). Chaque étude se conclut par un atelier qui demande soit d’implémenter une variante optimisée, soit de mesurer la performance sur un dataset synthétique.

#ExercicesCopier le lien

• Implémentez un tri fusion en place (en limitant les allocations).
• Construisez un heap minimal et testez-le sur un flux de données.