`TP7 : algorithmes de tris <../TP7.pdf>`_ ----------------------------------------- On s'intéressera aujourd'hui aux algorithmes de tris les plus courants : - **Tri par insertion**, - **tri rapide**, et tri rapide *"randomisé"*, - **sélection** de l'élément de rang k, - **tri par fusion**, deux versions, - **tri par comptage**. .. note:: *"Étudier des tris ? Encore ?"* - Les algorithmes de tris sont des exemples ultra-classiques d'algorithmes "de base" (manipulant des listes ou des tableaux de nombres), qu'il faut bien connaître. - On ne demande pas d'apprendre par cœur le code d'aucun de ces tris, mais le concept ou l'idée derrière chacun (indice : le nom aide pas mal...). - Même Barack Obama vous le dira, **les algorithmes de tris sont importants !** Démonstration en vidéo : .. youtube:: https://www.youtube.com/watch?v=k4RRi_ntQc8 -------------------------------------------------------------------------------- Documentation ^^^^^^^^^^^^^ .. automodule:: TP7 :members: :undoc-members: -------------------------------------------------------------------------------- Bonus : un tri *stupide* ? ^^^^^^^^^^^^^^^^^^^^^^^^^^ En bonus, je vous laisse étudier (et implémenter) cet algorithme de tri, mon préféré (mais pas le plus efficace) : :: Entrée : Tableau de nombres réels T, de taille n 1. Tant que T n'est pas trié: 2. Mélanger T Sortie : Tableau T, trié. Questions : ~~~~~~~~~~~ 1. L'algorithme termine-t-il ? Sur *toutes* les entrées ? Sur *aucune* entrée ? 2. L'algorithme est-il *déterministe* ou *probabiliste* ? S'il est *probabiliste*, peut-il ne jamais terminer (si oui, avec quelle probabilité ?) 3. *Estimer* la complexité optimale de l'étape 1 (vérifier si T est trié), et de l'étape 2 (mélanger T). Astuce / rappel : générer une permutation *aléatoire* :math:`\sigma \in \Sigma_n` prend un temps :math:`O(n)` (l'algorithme n'est pas évident, mais c'est possible). 4. Estimer le nombre *moyen* (probabiliste) de parcours de la boucle "Tant que", pour un tableau quelconque (tiré dans un certain univers :math:`\Omega` à préciser). 5. Conclure quant à la complexité *en moyenne* de ce tri (*"tri par mélanges répétés"*). 6. Est-ce un algorithme *optimal* ? *Presque* optimal ? Pour *tout* tableau ? Pour *presque* tout tableau ? 7. Ou bien est-ce l'`algorithme le plus stupide `_ auquel on peut penser ... ?! -------------------------------------------------------------------------------- Sortie du script ^^^^^^^^^^^^^^^^ .. note:: Les docstrings foirent un peu, à cause de mesures de temps d'execution qui sont hautement aléatoires, et de l'aléa utilisé dans les tests. .. runblock:: console $ python TP7.py Le fichier Python se trouve ici : :download:`TP7.py`.