Différences
Ci-dessous, les différences entre deux révisions de la page.
Prochaine révision | Révision précédente | ||
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 ===== | ===== Tri à bulles ===== | ||
- | * [[http://fr.wikipedia.org/ | + | * [[wp>fr: |
<note tip> | <note tip> | ||
===== Quicksort ===== | ===== Quicksort ===== | ||
+ | Version récursive de l' | ||
- | <sxh python; title : quicksort_01.py> | + | <code python quicksort_01.py> |
#! / | #! / | ||
# -*- coding: utf-8 -*- | # -*- coding: utf-8 -*- | ||
""" | """ | ||
- | Code compact de quicksort. | + | Code compact de la fonction |
""" | """ | ||
def quicksort(li): | def quicksort(li): | ||
- | if li == []: | + | if li == []: return [] |
- | | + | |
pivot = li[0] | pivot = li[0] | ||
equal = [pivot] | equal = [pivot] | ||
- | lesser = quicksort([x for x in li[1:] if x < pivot]) | + | lesser = quicksort([x for x in li[1:] if x <= pivot]) |
greater = quicksort([x for x in li[1:] if x > pivot]) | greater = quicksort([x for x in li[1:] if x > pivot]) | ||
return lesser + equal + greater | return lesser + equal + greater | ||
Ligne 29: | Ligne 29: | ||
from numpy import random | from numpy import random | ||
a=random.randint(0, | a=random.randint(0, | ||
- | print a,len(a) | + | print(a,len(a)) |
b=quicksort(a) | b=quicksort(a) | ||
- | print b,len(b) | + | print(b,len(b)) |
- | </sxh> | + | </ |
+ | |||
+ | 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]) | ||
+ | ... | ||
+ | </ | ||
+ | |||
+ | 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 : | Références : | ||
* [[http:// | * [[http:// | ||
- | * [[http://en.wikipedia.org/wiki/ | + | * [[wp> |
+ | |||
+ | ===== Comparaison des tris ===== | ||
+ | L' | ||
+ | |||
+ | {{ https:// | ||
+ | |||
+ | Cf. aussi cette autre visualisation : [[https://www.makeartwithpython.com/blog/ | ||
+ | | {{ https:// | ||
+ | |||
+ | ===== Algorithmes inefficaces ===== | ||
+ | * [[wp>fr: | ||
+ | |||
+ | ===== Références ===== | ||
+ | * Sources de codes (qualité à vérifier) [[https:// | ||
+ | * [[https:// |