Programmation impérative : TP 8

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

Listes chaînées

1. Proposer une procédure qui insère entre chaque paire d'éléments consécutifs d'une liste leur moitié.
2. Proposer une procédure qui prend en paramètre un élément et une liste supposée triée par référence, et qui insère par effet un nouveau maillon contenant l'élément dans la liste de sorte qu'elle reste triée.
3. 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.
4. Proposer une procédure qui prend en paramètre un maillon et une liste supposée triée, tous deux par référence, et qui insère par effet le maillon dans la liste de sorte qu'elle reste triée.
5. 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).
6. 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 strictement plus petits que pivot et dans *r2 les éléments plus grands ou égaux. 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.