Algorithmes de Tri et Analyse

Implémenter le tri par insertion et analyser sa complexité dans le meilleur et le pire des cas.

Implémenter l'algorithme du tri fusion (merge sort) et prouver sa complexité en O(n log n).

Implémenter l'algorithme du tri rapide (quicksort) en portant une attention particulière à la fonction de partition.

Analyser la complexité du tri rapide dans le meilleur cas, le cas moyen (intuitivement) et le pire cas.

Décrire la propriété d'un tas binaire (heap) et son implémentation à l'aide d'un tableau.

Implémenter les opérations d'un tas binaire et les utiliser pour réaliser le tri par tas (heapsort).

Expliquer et implémenter le tri par comptage (counting sort) et le tri par base (radix sort), en analysant leurs conditions d'application.

Démontrer la borne inférieure Ω(n log n) pour les tris par comparaison en utilisant le modèle de l'arbre de décision.