Bonjour,

J'ai récemment fait un programme de tri rapide avec le code suivant:

#Liste que l'on veut trier.
liste = [98, 56, 99, 2, 33, 45, 11, 63, 51, 33, 8, 28]

#Fonction de tri rapide, avec d et f les valeurs des indices du début et de la fin de la liste.
def tri(t, d, f):
    #Définition du pivot : valeur médiane de la série (ce qui explique qu'il est entier), tous les élements inférieurs se trouvent "à sa gauche" et tous les élements "à sa droite".
    pivot = t[int((d+f)/2)]
    #Définition de i et j, les compteurs permettant de trier dans toute la liste.
    i = d
    j = f
    #Tant que la recherche n'a pas été explicitement stoppée, elle continue.
    while True:
        #On effectue à la fois un tri au début et à la fin de la liste, et on se rapproche du pivot.
        while t[i]<pivot:
            i+=1
        while t[j]>pivot:
            j-=1
        #On arrête le tri quand une valeur dépasse l'autre, ici quand i dépasse j.
        if i>j:
            break
        #Si c'est j qui dépasse i, on inverse les valeurs: i se retrouve avec la valeur correspondante de j, et j avec celle de i. Ainsi, on reclasse bel et bien les valeurs dans l'ordre croissant.
        if i<j:
            t[i], t[j] = t[j], t[i]
        i+=1
        j-=1
    #Lorsque le premier tri a été fait, on recommence soit avec un nouvel indice de début (i) soit de fin (j).
    if d<j:
        tri(t, d, j)
    if i<f:
        tri(t, i, f)

#Programme principal, avec d = 0 et f = n-1 (len correspond au nombre de valeurs présentes dans la série).
t = liste
d = 0
f = len(t)-1
tri(t, d, f)
print(t)

Seulement, j'aimerais faire en sorte que la liste soit triée dans l'ordre décroissant, et j'ai beau chercher je ne comprends pas ce que je dois modifier...Je ne sais même pas si je dois entièrement refaire le programme.

Salut,

Sans QS, ASC

sorted(liste)

DESC

sorted(liste, reverse=True)

Sur ton script de QS, suffit juste d'inverse ta comparaison lignes 14 et 16

while t[i]>pivot:

while t[j]<pivot:

-
Edité par KriSpiX 18 février 2016 à 15:36:00

tiens je viens de comprendre ce qu'est une methode par pivot pour trier un tableau ou une liste ! (methode de KriSpik beaucoup plus simple a utiliser en python)

merci

@+