from random import randint

############################################################################
#  TRI RAPIDE EFFICACE EN ESPACE
############################################################################
def triRapideEfficace(liste):
    """
    fonction qui initialise la fonction récursive de tri rapide d'une liste.
    """
    trierEfficacement(liste, 0, len(liste)-1)

def trierEfficacement(liste, indiceDebut, indiceFin):
    """
    fonction récursive qui trie une liste en utilisant la méthode trie rapide.
    """
    if (indiceFin <= indiceDebut):
        return
    indicePivot = randint(indiceDebut, indiceFin)
    pivot = liste[indicePivot]
    indicePivot = partitionnerEfficacement(liste, pivot, indiceDebut, indicePivot, indiceFin)
    trierEfficacement(liste, indiceDebut, indicePivot-1)
    trierEfficacement(liste, indicePivot+1, indiceFin)

def partitionnerEfficacement(liste, pivot, indiceDebut, indicePivot, indiceFin):
    """
    fonction qui partitionne une liste en fonction d'un pivot en mettant à gauche
    du pivot les éléments plus petits que le pivot et à droite les éléments plus
    grand. L'indice du pivot est susceptible d'être modifié au cours du traitement ;
    il est donc renvoyé par cette fonction.
    """
    termine = False
    indiceCourant = indiceDebut
    while indiceCourant <= indiceFin:
        if liste[indiceCourant] > pivot and indiceCourant < indicePivot:
            liste[indicePivot] = liste[indiceCourant]
            liste[indiceCourant] = liste[indicePivot-1]
            liste[indicePivot-1] = pivot
            indicePivot = indicePivot - 1
        elif liste[indiceCourant] < pivot and indiceCourant > indicePivot:
            liste[indicePivot] = liste[indiceCourant]
            liste[indiceCourant] = liste[indicePivot+1]
            liste[indicePivot+1] = pivot
            indicePivot = indicePivot + 1
        else:
            indiceCourant = indiceCourant + 1
    return indicePivot

############################################################################
#  TRI RAPIDE NAIF
############################################################################
def trier(liste):
    """
    fonction récursive qui trie une liste en utilisant la méthode trie rapide.
    """
    if liste == []:
        return []
    indicePivot = randint(0, len(liste)-1)
    pivot = liste[indicePivot]
    liste[indicePivot:indicePivot+1] = []
    partition = partitionner(liste, pivot)
    gaucheTriee = trier(partition[0])
    droiteTriee = trier(partition[1])
    return gaucheTriee + [pivot] + droiteTriee

def partitionner(liste, pivot):
    petits = []
    grands = []
    for valeur in liste:
        if valeur <= pivot:
            petits.append(valeur)
        else:
            grands.append(valeur)
    return (petits, grands)

liste = []
for i in range(0, 30):
    liste.append(randint(1,100))

print("Liste de départ :")
print(liste)
liste1 = liste[:]
print("Résultat du tri rapide efficace en espace :")
triRapideEfficace(liste1)
print(liste1)
print("Résultat du tri rapide naïf :")
liste2 = trier(liste)
print(liste2)