suivant: Exercice 17 - Tri
monter: L'heure du code
précédent: Exercice 15 - Une
Table des matières
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 ?
suivant: Exercice 17 - Tri
monter: L'heure du code
précédent: Exercice 15 - Une
Table des matières
klaus
2010-08-05