1A.algo - Quicksort

Links: notebook, html, PDF, python, slides, GitHub

Cet énoncé a pour objectif de présenter l’algorithme de tri quicksort qui permet de trier par ordre croissant un ensemble d’éléments (ici des chaînes de caractères) avec un coût moyen.

Lorsqu’on parle de coût moyen, cela signifie que le coût n’est pas constant en fonction de la dimension du problème. Ici, le coût moyen désigne le coût moyen d’un tri :raw-latex:`\textit{quicksort}` obtenu en faisant la moyenne du coût du même algorithme sur toutes les permutations possibles de l’ensemble de départ. en O(n \ln n)n est le nombre d’éléments à classer. Le tri quicksort apparaît rarement sous la forme d’un graphe : il est plus simple à programmer sans les graphes mais il est plus simple à appréhender avec les graphes. Dans cette dernière version, l’algorithme insère un à un les éléments d’une liste à trier dans un graphe. Chaque noeud de ce graphe est relié à deux autres noeuds.

  • Un noeud avant ou "<" qui permet d’accéder à des éléments classés avant celui de ce noeud.
  • Un noeud apres ou ">" qui permet d’accéder à des éléments classés après celui de ce noeud.

Les noeuds avant et apres sont appelés les successeurs. Le terme opposé est prédécesseur. Ces deux noeuds ont nécessairement un prédécesseur mais un noeud n’a pas forcément de successeurs. S’il en avait toujours un, l’arbre serait infini.

from jyquickhelper import add_notebook_menu
add_notebook_menu()

Q1 : classe

On cherche à construire une classe ayant pour nom NoeudTri et qui contient une chaîne de caractères initialisée lors de la création de la classe : n = NoeudTri("essai").

Q2 : str

On écrit la méthode __str__ de sorte que l’instruction print(n) affiche la chaîne de caractères que contient n.

Q3 : avant, après

On cherche maintenant à définir d’autres noeuds, reliés à des attributs avant et apres. On suppose que les noeuds utilisent l’attribut mot, on crée alors une méthode insere(s) qui :

  • Si s < self.mot, alors on ajoute l’attribut avant = NoeudTri(s).
  • Si s > self.mot, alors on ajoute l’attribut apres = NoeudTri(s).

Q4 : str

La méthode __str__ n’affiche pour le moment qu’un mot. Il s’agit maintenant de prendre en compte les attributs avant et apres afin que l’instruction print(n) affiche avant.__str__() et apres.__str__(). Il faudra également faire en sorte que la méthode avant.__str__() ne soit appelée que si l’attribut avant existe. Comme la liste des mots à trier est finie, il faut bien que certains noeuds n’aient pas de successeurs. Qu’est-ce qu’affiche le programme suivant ?

racine = NoeudTri("un")  # noeud tri n'est pas encore défini
racine.insere ("unite")
racine.insere ("deux")
print(racine)
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-6-2f354be36812> in <module>()
----> 1 racine = NoeudTri("un")  # noeud tri n'est pas encore défini
      2 racine.insere ("unite")
      3 racine.insere ("deux")
      4 print(racine)

NameError: name 'NoeudTri' is not defined

Q5 : insere

Est-il possible de trier plus de trois mots avec ce programme ? Que faut-il modifier dans la méthode insere afin de pouvoir trier un nombre quelconque de mots ?

Q6 : exception

Ajouter le code nécessaire afin que la méthode insere génère une exception lorsqu’un mot déjà présent dans l’arbre est à nouveau inséré.

Q7 : graph

On se propose de construire une image représentant l’arbre contenant les mots triés par l’algorithme quicksort. Cette représentation utilise le module blocdiag ou on peut utiliser la fonction draw_diagram.

from pyensae.graphhelper import draw_diagram
img = draw_diagram("""
        blockdiag {
            A -> B -> C -> D;
            A -> E -> F;
            F -> G [label = "edge-FG"];
            E [label="label-E"]
        }
        """)
img
../_images/td1a_quicksort_13_0.png