.. _td1aquicksortrst:

===================
1A.algo - Quicksort
===================


.. only:: html

    **Links:** :download:`notebook <td1a_quicksort.ipynb>`, :downloadlink:`html <td1a_quicksort2html.html>`, :download:`python <td1a_quicksort.py>`, :downloadlink:`slides <td1a_quicksort.slides.html>`, :githublink:`GitHub|_doc/notebooks/td1a_algo/td1a_quicksort.ipynb|*`


Cet énoncé a pour objectif de présenter l’algorithme de tri
`quicksort <https://fr.wikipedia.org/wiki/Tri_rapide>`__ 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 :math:`O(n \ln n)` où
:math:`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.

.. code:: ipython3

    from jyquickhelper import add_notebook_menu
    add_notebook_menu()






.. contents::
    :local:





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 ?

.. code:: ipython3

    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 <http://blockdiag.com/en/>`__ ou on peut utiliser la
fonction
`draw_diagram <http://www.xavierdupre.fr/app/pyensae/helpsphinx/pyensae/graphhelper/blockdiag_helper.html?highlight=draw_diagram#pyensae.graphhelper.blockdiag_helper.draw_diagram>`__.

.. code:: ipython3

    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




.. image:: td1a_quicksort_17_0.png