Programmation impérative : TP 8

Pour ces deux exercices, on travaillera sur des listes d'entiers.

Listes chaînées

1. Proposer une fonction qui insère entre chaque paire d'éléments consécutifs d'une liste leur moitié.
2. Proposer une fonction qui retourne une liste comportant les mêmes éléments mais triée (par insertion) par ordre croissant qu'une liste passée en paramètre. On ne modifiera pas la liste passée en paramètre.
3. Proposer une procédure dont l'effet est de trier (par insertion) par ordre croissant une liste passée en paramètre. On ne fera pas d'allocation dynamique (même indirectement via les constructeurs de listes).
4. Crible d'Ératosthène
   1. Proposer une fonction qui sur la donnée d'un entier n retourne une liste contenant tous les entiers de 2 à n, 2 étant en tête de liste.
   2. Proposer une procédure qui sur la donnée d'un entier et d'une liste, supprime tous les éléments de la liste qui sont des multiples de l'entier.
   3. Proposer une fonction implémentant le crible d'Ératosthène pour obtenir la liste des nombres premiers de 2 à n.

Tri rapide

1. Proposer une procédure qui sur la donnée d’une liste l, d'un entier pivot et de deux pointeurs sur liste r1 et r2 a pour effet de découper l en mettant dans *r1 les éléments plus petits ou égaux à pivot et dans *r2 les éléments strictement plus grands. On ne fera pas d'allocation dynamique.
2. (Vu en cours.) Implémenter une fonction qui concatène deux listes.
3. Implémenter le tri rapide : on choisit comme pivot le premier élément de la liste ; on sépare la suite de la liste en deux listes contenant les éléments plus petits ou égaux au pivot, et plus grands ; on tri récursivement les deux sous-listes ; on concatène finalement la première sous-liste triée, le pivot et la deuxième sous-liste triée.