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 [2016/11/06 09:47] – villersd
@@ Ligne 10: / Ligne 10: @@
 ===== Quicksort =====
+Version récursive de l'algorithme, avec un pivot arbitraire.
 <sxh python; title : quicksort_01.py>
@@ Ligne 15: / Ligne 16: @@
 # -*- 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 32: / Ligne 32: @@
 b=quicksort(a)
 print b,len(b)
+</sxh>
+On peut aussi rendre la fonction encore plus compacte, mais moins lisible :
+<sxh 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])
+...
 </sxh>
@@ Ligne 37: / Ligne 48: @@
   * [[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]]
+===== 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 }}
+===== Sources de codes =====
+(qualité à vérifier)
+  * [[https://github.com/thecodershub/algorithms/tree/master/python/sort]]