Skip to main content Informatique en prépa - Lycée Malherbe 

4.1- TP - Tournoi des blobs

On vous a donné la tâche (très importante) d'organiser le tournois des blobs. Les blobs sont nombreux, et s'affrontent d'une manière mysterieuse que seuls eux maitrisent.

L'issue des affrontement est entièrement déterministe :

Votre objectif ? Établir le grand classement des blobs !

classement.png

Implémentation python

  • Vous devez commencer par importer les éléments du module "blob", avec la ligne from blob import *.

  • Vous disposerez ensuite d'une liste de tous les blobs (ils sont 500), à laquelle vous pouvez accéder avec la fonction get_blobs().

  • Pour faire combattre deux blobs, on les compare : blob1 > blob2 vaut True si blob1 gagne le combat contre blob2, et False sinon. De même, blob1 < blob2 vaut True si c'est blob2 qui gagne. Chaque comparaison est un combat.

  • Lorsque vous affichez un blob, il est identifié par son prénom (pris dans la liste officielle des prénoms en France depuis 2010, je n'ai rien inventé). Bien sûr, les blobs portent leur prénoms sans considération de genre, ce sont des blobs après tout.

Python

Loading editor...

from blob import *
Python

Loading editor...

blobs = get_blobs()
N = len(blobs)
Question 1

Choisissez deux blobs de votre choix, et affichez-les.

Python

Loading editor...

Python

Loading editor...

Python

Loading editor...

Question 2

Faites-les s'affronter, en les comparant. Qui gagne ?

Voir le combat

Pour voir le combat en animation, utilisez afficher_combat(blob1, blob2) : elle renvoie le vainqueur. Plus un blob est grand, plus il est fort...

Python

Loading editor...

On va maintenant s'intéresser au tournois.

Vous avez peut-être remarqué une forte similarité entre ce problème, et celui du tri d'une liste ! Donc inspirez-vous librement du cours sur les tris.

I. Les tris quadratiques

Des classements en place

Dans tout ce TP, les classements se font en place : on ne crée pas de nouvelle liste, on modifie directement la liste blobs, en échangeant des blobs de place. À la fin, blobs[0] est le meilleur blob, blobs[1] le deuxième, etc.

Pour échanger les blobs d'indices i et j, on écrit : blobs[i], blobs[j] = blobs[j], blobs[i].

I.1. Première idée

On propose un premier moyen de réaliser le tournois :

bulle.png

Question 3

Écrivez une fonction, qui prend en argument

  • la liste des blobs
  • un indice i < len(blobs) - 1 Et qui réalise l'affrontement entre le blob à l'emplacement i, et celui à l'emplacement i + 1. Si le blob d'indice i + 1 gagne, votre fonction échange les deux blobs, afin que le gagnant soit le premier des deux dans la liste. La fonction ne renvoie rien : elle modifie la liste.
Python

Loading editor...

Question 4

En déduire une fonction passe(blobs) qui applique cette procédure à chaque blob de la liste : pour i allant de 0 (inclus) à len(blobs) - 1 (exclu), le blob d'indice i affronte son voisin de droite. Remarquez qu'après une passe, le plus faible des blobs est forcément arrivé à la fin de la liste !

Python

Loading editor...

Vérification : passe
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Question 5

Combien de fois faudra-il répèter cette fonction pour que notre liste contienne le classement final ?

Écrivez ensuite une fonction classement_bulle qui réalise le classement en suivant ces étapes, puis affichez les 10 premiers blobs du classement.

Et non ! Ca ne suffit pas. Par exemple, que ce passe-il si les blobs sont en ordre inverse au départ ?

Oui ! Il faut bien le faire N fois.

Ca fait beaucoup quand même non ?

Python

Loading editor...

Visualiser le classement

La fonction animer_classement(fonction, n) applique votre fonction de classement à une liste de n blobs, puis anime son déroulement : à chaque combat (chaque comparaison), les deux blobs se foncent dessus, et le vainqueur saute sur le perdant. Puis les blobs se déplacent à leur nouvelle place dans le classement. Si votre fonction crée d'autres listes de blobs, elles sont affichées en dessous, avec le nom de leur variable.

Essayez-la avec chacun de vos classements !

Python

Loading editor...

animer_classement(classement_bulle, 16)
Question 6

Quel est l'ordre de grandeur du nombre de comparaisons (de combats) faites par votre fonction, en fonction du nombre de blobs ?

Non !

Oui !

En soi, c'est vrai. Mais en général, on évite d'utiliser des formules inutilement compliquées dans les .

Vous l'aurez peut-être remarqué, mais on viens d'implémenter le tri à bulle !

Si vous ne voyez pas le lien, essayez de revoir la fonction du tri à bulle du cours.

Maitenant, on va faire la même chose avec les autres tris.

Récupérer à nouveau la liste des blobs non triés :

Python

Loading editor...

blobs = get_blobs()

I.2. Tri par sélection

Cette fois, l'idée est d'abord de trouver le blob gagnant, puis le suivant, et ainsi de suite.

Question 7

Écrivez une fonction selection qui prend en argument

  • une liste blobs
  • un indice 0 <= k < len(blobs)

Et qui renvoie l'indice du blob le mieux classé de la liste blobs entre les indices k (inclus) et len(blobs) (exclu). On pourra garder en mémoire l'indice du meilleur blob trouvé jusqu'ici, et le faire combattre avec chacun des blobs suivants.

Python

Loading editor...

Vérification : selection
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Question 8

En déduire une fonction classement_selection qui réalise le classement, en utilisant la fonction de la question précédente : pour k allant de 0 (inclus) à len(blobs) - 1 (exclu), on cherche le meilleur blob parmi ceux d'indices k (inclus) à len(blobs) (exclu), et on l'échange avec le blob d'indice k. Ainsi, après ce tour, les blobs d'indices 0 (inclus) à k + 1 (exclu) sont les k + 1 meilleurs, dans l'ordre.

Affichez les dix premiers blobs, et assurez-vous que le résultat est le même que pour le classement bulle !

Python

Loading editor...

Python

Loading editor...

animer_classement(classement_selection, 16)
Question 9

Quel est l'ordre de grandeur du nombre de comparaisons (de combats) faites par votre fonction, en fonction du nombre de blobs ?

Non !

Oui !

En soi, c'est vrai. Mais en général, on évite d'utiliser des formules inutilement compliquées dans les .

Python

Loading editor...

blobs = get_blobs()

I.3. Tri par insertion

Oui, encore un tri... Mais bon, cette fois vous avez compris le principe, ça devrait aller vite !

Question 10

Écrivez une fonction insere(blobs, i) qui prend en argument la liste des blobs et un indice i. On suppose que les blobs d'indices 0 (inclus) à i (exclu) sont déjà classés entre eux. La fonction fait "reculer" le blob d'indice i jusqu'à sa place : tant qu'il bat son voisin de gauche, il échange sa place avec lui.

Après l'appel, les blobs d'indices 0 (inclus) à i + 1 (exclu) sont classés entre eux.

Python

Loading editor...

Vérification : insere
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Question 11

En déduire une fonction classement_insertion qui classe la liste des blobs (en place) : on insère successivement le blob d'indice 1, puis celui d'indice 2, etc. Au départ, le "classement partiel" ne contient que le blob d'indice 0.

Python

Loading editor...

Python

Loading editor...

animer_classement(classement_insertion, 16)
Question 12

Quel est l'ordre de grandeur du nombre de comparaisons (de combats) faites par votre fonction, en fonction du nombre de blobs ?

Non !

Oui !

En soi, c'est vrai. Mais en général, on évite d'utiliser des formules inutilement compliquées dans les .

II. Mais en vrai, qui fait un tournois comme ça ?

Les blobs, visiblement. Peut être qu'ils en ont marre de s'affronter pendant aussi longtemps, et qu'ils préfèreraient aller plus vite. Mais vous pouvez les aider à faire mieux !

On peut, par exemple, imaginer des mini tournois dans le grand tournois !

Question 13

En supposant qu'on ait deux classements de blobs distincts (par exemple, obtenus par deux mini tournois). Comment peut-on les combiner en un grand classement ?

Dans notre liste, les deux classements sont côte à côte : ce sont les blobs d'indices debut (inclus) à milieu (exclu), et ceux d'indices milieu (inclus) à fin (exclu). Écrivez une fonction fusion(blobs, debut, milieu, fin) qui les fusionne en un seul classement, des indices debut (inclus) à fin (exclu), en place (sans liste temporaire) :

  • on garde deux indices : i1, qui part de debut, et i2, qui part de milieu. Ce sont les meilleurs blobs de chaque classement qui ne sont pas encore à leur place définitive ;
  • on fait combattre les blobs d'indices i1 et i2 :
    • si le blob d'indice i1 gagne, il est à sa place : on avance i1 ;
    • sinon, le blob d'indice i2 doit passer devant tous les blobs restants du premier classement : on le fait reculer jusqu'à l'indice i1, en l'échangeant successivement avec son voisin de gauche. Les blobs restants du premier classement sont alors décalés d'une case vers la droite : on avance i1 et i2 ;
  • on s'arrête quand l'un des deux classements est épuisé (i1 == i2 ou i2 == fin) : les blobs restants sont déjà à leur place.
Python

Loading editor...

Vérification : fusion
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Question 14

Quel est l'ordre de grandeur du nombre de comparaisons (de combats) faites par votre fonction ? Avec la somme des longueurs des deux classements.

Pour les blobs, seuls les combats sont coûteux : se déplacer dans la liste ne leur coûte rien. Dans tout ce TP, on compte donc seulement les comparaisons (on ne compte pas les échanges).

Non, on doit tout de même parcourir les listes !

Oui !

Non ! D'où sortirais le log dans ce cas ?

Si c'est la cas, vous pouvez faire mieux ! Réfléchissez à votre fonction.

Fonctions récursives

En python, (et en informatique en général), on peut faire des fonctions récursives, c'est-à-dire qui s'appellent elles-mêmes.

Attention, pour ne pas boucler à l'infini, l'idée est d'appeller notre fonction sur des entrées de plus en plus petites !

Par exemple, on peut imaginer une fonction du tri par insertion qui classe les n premiers blobs de la liste en faisant les opérations suivantes :

  • si n vaut 0 ou 1, il n'y a rien à faire ;
  • sinon, on classe les n - 1 premiers blobs (avec la même fonction !) ;
  • puis on insère le blob d'indice n - 1, avec la fonction insere de la question 10.
def tri_insertion_rec(blobs, n):
    """Classe (en place) les n premiers blobs, par insertion, récursivement."""
    # cas de base : 0 ou 1 blob, déjà classé
    if n <= 1:
        return
    # on classe les n - 1 premiers blobs (un problème plus petit)
    tri_insertion_rec(blobs, n - 1)
    # puis on insère le blob d'indice n - 1
    insere(blobs, n - 1)

Pour classer toute la liste, on appelle tri_insertion_rec(blobs, len(blobs)).

On propose alors une nouvelle procédure de classement, pour classer les blobs d'indices debut (inclus) à fin (exclu) :

Question 15

Écrivez une fonction récursive classement_fusion_rec(blobs, debut, fin) qui réalise le classement de cette manière, puis une fonction classement_fusion(blobs) qui classe toute la liste (en appelant classement_fusion_rec avec les bons indices).

Python

Loading editor...

Python

Loading editor...

animer_classement(classement_fusion, 16)

III. Comparaison des classements

On aimerait maintenant comparer les manières de classer les blobs.

Compter les comparaisons

On vous met à disposition deux fonctions :

  • reinit_compteur() remet à zéro le compteur de comparaisons (de combats)
  • lire_compteur() renvoie le nombre de comparaisons depuis la dernière réinitialisation.
Question 16

Comptez le nombre de comparaisons dans chacun de vos tris. Que remarquez-vous ?

Python

Loading editor...

blobs = get_blobs()
reinit_compteur()

# à completer

print(lire_compteur())
Python

Loading editor...

Python

Loading editor...

Python

Loading editor...

Plus de blobs ?

Vous pouvez, optionellement, donner un argument à get_blobs pour dire combien de blobs vous voulez.

Courbes

Vous pouvez afficher des courbes :

  • importez le module matplotlib.pyplot avec import matplotlib.pyplot as plt
  • pour déclarer une courbe, plt.plot(X, Y, "r+"), où X et Y sont des listes de mêmes tailles contenant les ordonnées et abscisses de chaque point, "r" est la couleur de votre courbe, et "+" la forme des points ("-" pour une ligne, "." pour un point, etc).
  • pour afficher le résultat, plt.show(). Vous pouvez déclarer plusieurs courbes avant d'afficher le résultat, et elles seront alors sur le même graphique.
  • pour réinitialiser les courbes plt.clf(). Je vous conseille d'appeler cette fonction au début de chaque cellule qui affiche une courbe.
Question 17

Tracez les courbes du nombre de comparaisons des différents tri en fonction du nombre de blobs. Que remarquez-vous ?

Python

Loading editor...

Question 18

Tracez maintenant seulement la courbe du dernier tri (le tri fusion). Quelle forme a-t-elle ? À votre avis, quel est l'ordre de grandeur du nombre de comparaisons faites par cette fonction ?

Python

Loading editor...

Python

Loading editor...

Et Python, comment classe-t-il ?

Comme les blobs se comparent avec < et >, les fonctions de Python marchent aussi sur eux : max(blobs) renvoie le meilleur blob, et sorted(blobs, reverse=True) renvoie une nouvelle liste, classée du meilleur au moins bon. Comptez le nombre de comparaisons faites par sorted pour 500 blobs, et comparez avec vos classements ! Vous pouvez aussi essayer animer_classement(lambda blobs: sorted(blobs, reverse=True), 16).


Entrez le code donné en cours pour accéder à la solution :