====== Algorithmes de tri ======
Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon un ordre déterminé (Référence [[http://fr.wikipedia.org/wiki/Algorithme_de_tri|wikipedia]]).

Les tris sont intéressants du point de vue de l'apprentissage de l'algorithmique.

===== 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.

<code python quicksort_01.py>
#! /usr/bin/env python
# -*- coding: utf-8 -*-
"""
Code compact de la fonction quicksort. Exemple de tri d'éléments entiers.
"""

def quicksort(li):
    if li == []: return []
    pivot = li[0]
    equal = [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

from numpy import random
a=random.randint(0,1000,10)
print(a,len(a))
b=quicksort(a)
print(b,len(b))
</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]]
  * [[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