Différences

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

--- teaching:progappchim:tris [2015/03/30 13:37] – créée 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>
 ===== Quicksort =====
+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 -*-
 """
-Code compact de quicksort. Trie des éléments entiers différents (les doublons sont éliminés).
+Code compact de la fonction quicksort. Exemple de tri d'éléments entiers.
 """
 def quicksort(li):
-    if li == []:
+    if li == []: return []
-        return []
     pivot = li[0]
     equal = [pivot]
-    lesser = quicksort([x for x in li[1:] if x < pivot])
+    lesser = quicksort([x for x in li[1:] if x <= pivot])  # si x < pivot : élimination des doublons
     greater = quicksort([x for x in li[1:] if x > pivot])
     return lesser + equal + greater
@@ 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 :
+<code python>
+...
+def quicksort(li):
+    if li == []: return []
+    pivot = li[0]
+    return quicksort([x for x in li[1:] if x <= pivot]) + [pivot] + quicksort([x for x in li[1:] if x > pivot])
+...
+</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