Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

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 :

  1. D'abord nous allons créer une fonction est_triée qui renvoie si la liste est bien triée.
  2. Ensuite nous allons créer une fonction mélanger qui mélangera les éléments de la liste.
  3. 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 et False sinon.

Créer une fonction est_triée
1
2
3
4
5
6
7
8
def est_triée(liste):
#Ne pas toucher ce qui précède
#Les valeurs pour les variables en entrée seront automatiquement données
#Ecrire ci-dessous en n'oubliant pas d'indenter
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Mélange d'une liste

Pour mélanger une liste de longueur n, nous allons procéder de la manère suivante :

  1. On part du dernier élément de la liste (donc celui d'indice n-1).
  2. On choisit un nombre k au hasard entre 0 et n-1 et on échange liste[k] et liste[n-1].
  3. 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.

Créer une fonction mélanger
1
2
3
4
5
6
7
8
9
from random import randint
def mélanger(liste):
#Ne pas toucher ce qui précède
#Les valeurs pour les variables en entrée seront automatiquement données
#Ecrire ci-dessous en n'oubliant pas d'indenter
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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 :

  1. Tant que la liste n'est pas triée, on mélange la liste.
  2. 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...

Créer une fonction qui trie
1
2
3
4
5
6
7
8
9
10
11
from random import randint
#Copiez collez ci-dessous vos fonctions est_triée et mélanger
def mon_programme(liste):
#Les valeurs pour les variables en entrée seront automatiquement données
#Ecrire ci-dessous en n'oubliant pas d'indenter
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Open Source Your Knowledge: become a Contributor and help others learn. Create New Content