"""
Programme qui effectue un tri selon
l'algorithme de tri par pivot
aussi appelé quick sort
"""

# definition de la liste qu'on veut trier
liste = [70, 50, 30, 10, 20, 40, 60]

# fonction tri_fusion qui va s'appeller elle-même
# On appelle ça une fonction récursive
def tri_pivot(liste):
    if len(liste) <= 1:
        return liste
    liste_petits = []
    liste_grands = []
    # Définition du pivot:
    # 1er élément de la liste
    pivot = liste[0]
    # On parcourt tous les nombres
    # de la liste après le pivot
    for nombre in liste[1:]:
        if nombre < pivot:
            liste_petits.append(nombre)
        else:
            liste_grands.append(nombre)
    # On peut alors construire la réponse:
    # C'est la liste des petits triée,
    # le pivot, puis la liste des grands triée
    liste_triee = tri_pivot(liste_petits)
    liste_triee += [pivot]
    liste_triee += tri_pivot(liste_grands)
    return liste_triee

# Tri et affichage de notre liste:
print("Voici la liste triée:")
print(tri_pivot(liste))