Différences

Ci-dessous, les différences entre deux révisions de la page.

--- teaching:progappchim:tris [2015/03/31 09:09] – villersd
+++ teaching:progappchim:tris [2022/12/09 14:25] (Version actuelle) – villersd
@@ Ligne 5: / Ligne 5: @@
 ===== Tri à bulles =====
-  * [[http://fr.wikipedia.org/wiki/Tri_%C3%A0_bulles|Tri à bulles]]
+  * [[wp>fr:Tri_à_bulles|Tri à bulles]]
 <note tip>Adapter en Python le pseudo code proposé. La représentation du déroulement du tri est également intéressante à développer.</note>
@@ Ligne 12: / Ligne 12: @@
 Version récursive de l'algorithme, avec un pivot arbitraire.
-<sxh python; title : quicksort_01.py>
+<code python quicksort_01.py>
 #! /usr/bin/env python
 # -*- coding: utf-8 -*-
@@ Ligne 29: / Ligne 29: @@
 from numpy import random
 a=random.randint(0,1000,10)
-print a,len(a)
+print(a,len(a))
 b=quicksort(a)
-print b,len(b)
+print(b,len(b))
-</sxh>
+</code>
 On peut aussi rendre la fonction encore plus compacte, mais moins lisible :
-<sxh python>
+<code python>
 ...
 def quicksort(li):
@@ Ligne 43: / Ligne 43: @@
     return quicksort([x for x in li[1:] if x <= pivot]) + [pivot] + quicksort([x for x in li[1:] if x > pivot])
 ...
-</sxh>
+</code>
+Variante avec choix aléatoire du pivot (en fait de son index dans la numérotation de la liste) :
+<code python>
+...
+    pivot_index = randrange(len(li))
+    pivot = li[pivot_index]
+...
+</code>
 Références :
   * [[http://stackoverflow.com/questions/18262306/quick-sort-with-python]]
-  * [[http://en.wikipedia.org/wiki/Quicksort|Wikipedia en]] et [[http://fr.wikipedia.org/wiki/Tri_rapide|Wikipedia fr]]
+  * [[wp>Quicksort|Wikipedia en]] et [[wp>fr:Tri_rapide|Wikipedia fr]]
+===== Comparaison des tris =====
+L'efficacité des tris peut être comparée suivant la configuration des données initiales (avant tri) et leur nombre. Voir par exemple sur le site [[http://www.sorting-algorithms.com/|www.sorting-algorithms.com]], ou cette vidéo :
+{{ https://pbs.twimg.com/tweet_video/CZWNISuWkAEwE3q.mp4?600 }}
+Cf. aussi cette autre visualisation : [[https://www.makeartwithpython.com/blog/visualizing-sort-algorithms-in-python/|Sorting Algorithms Visualized in Python]], Using Python 3 and Scikit-Image
+|  {{ https://s3-us-west-2.amazonaws.com/makeartwithpython/bubble_s.gif }}  |  {{ https://s3-us-west-2.amazonaws.com/makeartwithpython/heap_s.gif }}  |  {{ https://s3-us-west-2.amazonaws.com/makeartwithpython/quick_s.gif }}  |
+===== Algorithmes inefficaces =====
+  * [[wp>fr:Tri_stupide|Tri stupide]] (bogo sort)
+===== Références =====
+  * Sources de codes (qualité à vérifier) [[https://github.com/thecodershub/algorithms/tree/master/python/sort]]
+  * [[https://realpython.com/sorting-algorithms-python/|Sorting Algorithms in Python]] Santiago Valdarrama, Real Python