This is a preview
This playground version isn't public and is work in progress.
Le tri stupide
Difficulté : Moyenne
Nous avons déjà vu des méthodes de tris dans des exercices précédents. Nous allons ici nous intéresser à une méthode de tri extrêmement peu efficace qui consiste à mélanger notre liste au hasard tant qu'elle n'est pas bien triée. C'est comme si on jetait un paquet de carte en l'air jusqu'à ce qu'il soit bien trié... Ca peu prendre du temps...
Nous allons procéder par étape :
- D'abord nous allons créer une fonction est_triée qui renvoie si la liste est bien triée.
- Ensuite nous allons créer une fonction mélanger qui mélangera les éléments de la liste.
- Enfin nous créerons le programme qui tri la liste (ou plutôt qui essaye de trier).
Vérifier si une liste est triée
Créer un programme est_triée qui prend en entrée une liste puis qui renvoie True
si elle est triée dans l'ordre croissant et False
sinon.
Entrée : Une liste .
Sortie : Renvoie (avec
return
)True
si liste est bien triée etFalse
sinon.
Mélange d'une liste
Pour mélanger une liste de longueur n, nous allons procéder de la manère suivante :
- On part du dernier élément de la liste (donc celui d'indice n-1).
- On choisit un nombre k au hasard entre 0 et n-1 et on échange liste[k] et liste[n-1].
- On recommence mais cette fois ci en considérant l'avant-dernier et un nombre k choisi entre 0 et n - 2 puis ensuite on recommence avec l'avant avant dernier etc. jusqu'à l'élément d'indice 1.
Ce mélange s'appelle mélange de Fisher-Yates. On peut trouver des précisions sur Wikipédia
Créer un programme mélanger qui prend en entrée une liste et renvoie une liste mélangée par cette méthode.
Aide
- Pour choisir un nombre aléatoirement entre 0 et n, on peut utiliser la fonction
randint(0,n)
. - Pour échanger des valeurs a et b, il suffit d'écrire
a,b=b,a
.
Entrée : Une liste.
Sortie : Renvoyer (avec
return
) la liste mélangée.
Le tri stupide
Maintenant qu'on a nos deux sous-fonctions, on peut créer un programme qui tri notre liste en procédant de la manière suivante :
- Tant que la liste n'est pas triée, on mélange la liste.
- Quand on trouve la liste triée, on la renvoie (avec
return
)
Copiez collez vos deux programmes précédents puis créez le programme qui renvoie la liste triée par une méthode de tri stupide.
Aide
Pour inverser True
et False
, on peut mettre not
devant.
Entrée : une liste.
Sortie : Une liste triée dans les temps (si on a de la chance). Si vous dépassez en temps, vous pouvez essayer plusieurs fois car ce tri étant basé sur la chance, il se peut que vous n'en n'ayez pas eu...