1A.algo - Quicksort#
Links: notebook
, html, 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ù 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’attributavant = NoeudTri(s)
.Si
s > self.mot
, alors on ajoute l’attributapres = 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