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().

• Un blob peut en combattre un autre avec blob1.combat(blob2). Cette fonction renvoie le vainqueur.

• 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.

Question 1

---

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

Question 2

---

Faite-les s'affronter. Qui gagne ?

Voir le combat

---

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

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].

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.

Question 4

---

En déduire une fonction passe(blobs) qui applique cette procédure à chaque blob de la liste : pour i allant de 0 à len(blobs) - 2, 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 !

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.

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, 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.

Essayez-la avec chacun de vos classements !

Question 6

---

Quelle est alors la complexité de votre fonction ?

Question 7

---

Écrivez une fonction selection qui prend en argument

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

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

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 à len(blobs) - 2, on cherche le meilleur blob parmi ceux d'indices k à len(blobs) - 1, et on l'échange avec le blob d'indice k. Ainsi, après ce tour, les blobs d'indices 0 à k 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 !

Question 9

---

Quelle est alors la complexité de votre fonction ?

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 à i - 1 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 à i sont classés entre eux.

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.

Question 12

---

Quelle est alors la complexité de votre fonction ?

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 à milieu - 1, et ceux d'indices milieu à fin - 1. Écrivez une fonction fusion(blobs, debut, milieu, fin) qui les fusionne en un seul classement, des indices debut à fin - 1, 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.

Question 14

---

Quelle est la complexité de votre fonction ? Avec la somme des longueur des deux sous-listes.

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 mesure donc la complexité en nombre de combats (on ne compte pas les échanges).

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 mesure donc la complexité en nombre de combats (on ne compte pas les échanges).

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)).

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).

Compter les combats

---

On vous met à disposition deux fonctions :

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

Question 16

---

Comptez le nombre de combats dans chacuns de vos tris. Que remarquez-vous ?

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 ?

Question 18

---

Tracez maintenant seulement la courbe du dernier tri (le tri fusion). Quelle forme a-elle ? À votre avis, quelle est la complexité de cette fonction ?