C18.2 : Tri par sélection
L'algorithme de tri par sélection est un algorithme classique qui permettent de trier une liste.
Principe
Algorithme
🖊️ Repérer les actions qui sont répétées.
🖥️ Proposer une fonction qui prend une liste en paramètre et modifie cette liste pour qu'à la fin de l'exécution de la fonction la liste soit triée par ordre croissant.
🖥️ Compléter avec le programme principal qui permet de tester la fonction avec une liste de 20 nombres entiers choisis aléatoirement entre 0 et 99.
Analyse de l'algorithme
Terminaison de l'algorithme
🖊️ Démontrer la terminaison de l'algorithme.
Correction de l'algorithme
🖊️ Proposer un invariant pour chacune des deux boucles.
Coût
🖊️ Pour quelle configuration de liste l'algorithme fait-il le moins de comparaison ? Dans ce cas combien en fait-il ?
🖊️ Pour quelle configuration de liste l'algorithme fait-il le plus de comparaison ? Dans ce cas, combien en fait-il ?
Pour aller plus loin
Lien : Algorithmes de tri
Lien : Algorithmes de tri animés