C11.1 : Rappels sur les algorithmes de tri de première
Tri par sélection
Principe
Dans cet algorithme, il s'agit de rechercher la plus petite valeur de la partie non triée de la liste et de l'insérer à la suite de la partie déjà triée de la liste... puis de recommencer.
Lien : Visualisation du principe du tri par sélection.
Codage de l'algorithme "en place"
Proposer une fonction, basée sur l'algorithme de tri par sélection, qui permet de trier "en place" une liste passée en paramètre, c'est à dire en modifiant directement cette liste.
Coût de l'algorithme
1) Pour quelle configuration de liste l'algorithme fait-il le moins de comparaison ? Dans ce cas combien en fait-il ?
2) Pour quelle configuration de liste l'algorithme fait-il le plus de comparaison ? Dans ce cas, combien en fait-il ?
Preuve de l'algorithme
1) Démontrer la terminaison de l'algorithme.
2) Proposer un invariant pour chacune des deux boucles.
Tri par insertion
Principe
Dans cet algorithme, il s'agit de prendre les valeurs de la liste les unes après les autres et de les insérer de façon à ce qu'elles forment une portion triée de liste.
Lien : Visualisation du principe du tri par insertion.
Codage de l'algorithme "en place"
Proposer une fonction, basée sur l'algorithme de tri par sélection, qui permet de trier "en place" une liste passée en paramètre, c'est à dire en modifiant directement cette liste.
Coût de l'algorithme
1) Pour quelle configuration de liste l'algorithme fait-il le moins de comparaison ? Dans ce cas combien en fait-il ?
2) Pour quelle configuration de liste l'algorithme fait-il le plus de comparaison ? Dans ce cas, combien en fait-il ?
Preuve de l'algorithme
1) Démontrer la terminaison de l'algorithme.
2) Proposer un invariant pour chacune des deux boucles.