TD d'informatique No. 5 : Trions des listes
Patrick Gros -- Patrick.Gros@irisa.fr
Didier Le Botlan -- didier.le_botlan@inria.fr
Lundi 11 décembre 2000
Exercice
Vous avez appris comment trier des tableaux et manipuler des
listes. Mélangeons les deux et trions des listes. On considère les mêmes
listes que la semaine dernière, mais on les affichera avec l'élément de tête
en premier. Écrire un fonction de tri par sélection, une fonction de tri par
insertion et une fonction de tri rapide (quicksort).
Remarque :
ces fonctions peuvent mélanger des aspects itératifs et
récursifs. Visez au plus simple selon les cas. L'emploi de fonctions
auxiliaires peut aussi simplifier les choses parfois.
Rappels :
Le tri par sélection consiste à chercher le plus petit
élément de la liste, à le mettre en tête de la liste résultat, et à recommencer
avec la liste initiale dont le minimum a été enlevé. Le tri par insertion
consiste à construire pas à pas la liste résultat, en insérant un à un les
éléments de manière à ce que le résultat soit trié. Le tri rapide consiste à
prendre un élément appelé pivot, à mettre avant (resp. après) les éléments
plus petits (resp. plus grands ou égaux), puis à recommencer le tri sur ces
deux parties de listes.
This document was translated from LATEX by
HEVEA.