informatique (tronc commun des prépas scientifiques) · Chapitre 9 · Application directe du cours
La stabilité, sur pièces
Les tris · niveau 1 (application)
Énoncé
On souhaite trier par note les fiches suivantes : . Montrer que le tri par sélection (avec comparaison sur la note) n'est pas stable en identifiant le moment de l'échange fautif.
Corrigé
- Étape : On cherche le minimum sur les notes . Le minimum est (Alice). On l'échange avec la position (Bob) .
- Étape : On cherche le minimum sur la fin. Bob et Chloé ont la même note de . Le tri se termine. Le résultat est . Bob, qui était situé avant Chloé dans le tableau initial, se retrouve après elle dans le tableau trié. Le grand échange à distance du tri par sélection a fait sauter Bob par-dessus Chloé, violant la stabilité.
Exercices semblables
- Compter les inversions en corrigé
- Le tri par comptage stable, et le tri par base corrigé
- Que vaut ? La borne, au plus près corrigé
- Deux déroulés corrigé
- Dérouler une fusion corrigé