Exercice 16 - Tri par insertion

Nous allons implémenter le tri par insertion d'une liste chaînée : Vous utiliserez les sous-programmes suivants et n'utiliserez aucune boucle, seule la récursivité est autorisée.

• link* insert(link* list, link* item, int (*estInf)(void*, void* )), insère dans la liste list triée le maillon item. On a estInf(i, j) si et seulement si la clé de i est strictement inférieure à celle de j.
• link* triInsertion(link* list, int (*estInf)(void*, void*)), trie par insertion la liste list en utilisant la fonction de comparaison estInf.
• void linkedListSort(linkedList* l, int (*estInf)(void*, void*)), trie la liste l en modifiant le chaînage, vous n'oublierez pas de mettre à jour l->first et l->last.
• Identifez le pire des cas et observez la façon dont le temps d'exécution croît avec le nombre de maillons. Est-ce que cela corrobore les conclusions théoriques ?