Différences
Ci-dessous, les différences entre deux révisions de la page.
Prochaine révision | Révision précédente Prochaine révisionLes deux révisions suivantes | ||
teaching:progappchim:tris [2015/03/30 13:37] – créée villersd | teaching:progappchim:tris [2015/03/31 09:09] – villersd | ||
---|---|---|---|
Ligne 10: | Ligne 10: | ||
===== Quicksort ===== | ===== Quicksort ===== | ||
+ | Version récursive de l' | ||
<sxh python; title : quicksort_01.py> | <sxh python; title : quicksort_01.py> | ||
Ligne 15: | Ligne 16: | ||
# -*- 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 32: | Ligne 32: | ||
b=quicksort(a) | b=quicksort(a) | ||
print b,len(b) | print b,len(b) | ||
+ | </ | ||
+ | |||
+ | 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]) | ||
+ | ... | ||
</ | </ | ||