S'il s'agit de trier une liste simple L, il n'est pas utile d'utiliser autre chose que L.sort() de Python qui est très très efficace.
Mais il arrive des cas où l'on veut trier selon des critères particuliers, et là, on a besoin d'une fonction de tri performante.
Voilà une fonction de tri basée sur le tri rapide de Hoare (quicksort) .
Ce tri est effectivement très rapide. Référence pour la définition: http://fr.wikipedia.org/wiki/Quicksort
Le code suivant applique assez fidèlement la définition de la méthode.
Attention: il modifie la liste donnée en paramètre.
Le choix du pivot est important: l'algorithme est d'autant plus efficace qu'on choisit un pivot qui sera effectivement au milieu de la partie de liste triée.
la fonction est récursive, mais on peut trier des listes de 100000 éléments sans problème sous Python.
Voilà le code proposé:
#!/usr/bin/python # -*- coding: utf-8 -*- def trirapide(L): """trirapide(L): tri rapide (quicksort) de la liste L""" def trirap(L, g, d): pivot = L[(g+d)//2] i = g j = d while True: while L[i]<pivot: i+=1 while L[j]>pivot: j-=1 if i>j: break if i<j: L[i], L[j] = L[j], L[i] i+=1 j-=1 if g<j: trirap(L,g,j) if i<d: trirap(L,i,d) g=0 d=len(L)-1 trirap(L,g,d)
Voilà comment on peut tester cette fonction:
import random import time # fabrication d'une liste de nmax valeurs aléatoires nmax=1000 L=[] for i in xrange(0,nmax): L.append(random.randint(1000,9999)) # à décommenter pour vérifier l'efficacité avec une liste déjà triée #L.sort() # à décommenter en plus de L.sort() pour une liste triée à l'envers #L.reverse() # tri avec affichage du temps passé tps=time.clock() trirapide(L) print time.clock()-tps # vérification que le tri est correct et affichage si erreurs for i in xrange(1,nmax): if L[i]<L[i-1]: print "erreur index ",i, L[i] # affichage de la liste triée for i in xrange(1,nmax): print L[i],
Efficacité du tri:
Pour des listes de 1000 éléments au hasard il est seulement un peu meilleur (-20%) que le tri par insertion avec recherche par dichotomie. Par contre, pour des listes plus importantes, il est plus rapide:
En fait, sur des petites listes (<20 éléments), il a réputation d'être moins efficace que le tri par insertion. Mais sur les très grandes listes, il est impressionnant!
Il est même assez efficace sur des listes déjà triées. Par exemple avec 10000 éléments:
La solution simple est d'utiliser la fonction précédente sur une copie de la liste:
R=list(L) trirapide(R)
Attention: n'oubliez pas le “list()”, parce que sinon, la modification sur R sera répercutée sur L. En fait, le “list()” fait une copie dite “superficielle” de la liste L.
On peut aussi modifier la fonction de tri précédente pour lui faire retourner un liste triée sans toucher à la liste d'origine. Cela n'a nécessité ici que la modification des 3 dernières lignes:
#!/usr/bin/python # -*- coding: utf-8 -*- def trirapide(L): def trirap(L, g, d): pivot = L[(g+d)//2] i = g j = d while True: while L[i]<pivot: i+=1 while L[j]>pivot: j-=1 if i>j: break if i<j: L[i], L[j] = L[j], L[i] i+=1 j-=1 if g<j: trirap(L,g,j) if i<d: trirap(L,i,d) g=0 d=len(L)-1 R=list(L) trirap(R,g,d) return R
Utilisation:
R=trirapide(L)
Ici, on ne modifie pas la liste à trier, mais on veut récupérer une liste d'index qui permettra de retrouver les valeurs de la liste triées sans la modifier.
On va créer au départ cette liste d'index X de la façon suivante:
# liste d'index X pour une liste L donnée X=[] for i in xrange(0,len(L)): X.append(i)
Quand on a cette liste d'index:
Voilà le nouveau code de tri indexé:
#!/usr/bin/python # -*- coding: utf-8 -*- def trirapideindexe(L): def trirap(L, g, d): pivot = L[X[(g+d)//2]] i = g j = d while True: while L[X[i]]<pivot: i+=1 while L[X[j]]>pivot: j-=1 if i>j: break if i<j: X[i], X[j] = X[j], X[i] i+=1 j-=1 if g<j: trirap(L,g,j) if i<d: trirap(L,i,d) g=0 d=len(L)-1 X=[] for i in xrange(0,len(L)): X.append(i) trirap(L,g,d) return X
Pour l'utiliser, quand on a une liste L à trier, on fait simplement:
X=trirapideindexe(L)
Et on récupère la liste d'index X qui permet de retrouver toutes les valeurs de L triées quand on les appelle par L[X[i]].
Et voilà comment on peut vérifier la fonction ci-dessus:
# fabrication d'une liste de 1000 valeurs aléatoires L=[] nmax=1000 for i in xrange(0,nmax): L.append(random.randint(1000,9999)) # à décommenter pour vérifier l'efficacité avec une liste déjà triée #L.sort() # à décommenter en plus de L.sort() pour une liste triée à l'envers #L.reverse() # tri avec affichage du temps de tri tps=time.clock() X=trirapideindexe(L) print time.clock()-tps # vérification que le tri est correct et affichage d'éventuelles erreurs for i in xrange(1,nmax): if L[X[i]]<L[X[i-1]]: print "erreur index ",i, L[i], L[X[i]] # affichage de la liste triée for i in xrange(1,nmax): print L[X[i]], # affichage de la liste initiale print for i in xrange(1,nmax): print L[i],
Jusqu'à présent, à part le trié indexé, ce qu'on a fait aurait pu tout aussi bien être fait avec la fonction sort() de Python.
Mais quand on a une liste d'éléments plus complexes, il faut une fonction tri adaptée. Voyons 2 exemples:
On considère la liste suivante:
L=[[5,9,3], [2,8,4], [5,1,0], ..., [3,0,7]]
Cette liste est composée de sous-listes de 3 nombres. On veut avoir la liste triée selon l'ordre des 2èmes nombres. C'est à dire que [3,0,7] est avant [5,1,0], puis on aura [2,8,4] et enfin [5,9,3].
Comme pour le tri indexé, on va examiner les éventuels changements des 4 lignes de la fonction de tri:
Ce qui donnera comme fonction de tri (vous l'appelez comme vous voulez):
#!/usr/bin/python # -*- coding: utf-8 -*- def trirapidesousliste(L): def trirap(L, g, d): pivot = L[(g+d)//2][1] i = g j = d while True: while L[i][1]<pivot: i+=1 while L[j][1]>pivot: j-=1 if i>j: break if i<j: L[i], L[j] = L[j], L[i] i+=1 j-=1 if g<j: trirap(L,g,j) if i<d: trirap(L,i,d) g=0 d=len(L)-1 trirap(L,g,d)
Et voilà comment la vérifier:
import random import time # fabrication d'une liste de 1000 sous-listes de 3 valeurs aléatoires L=[] nmax=1000 for i in xrange(0,nmax): L.append([random.randint(1000,9999),random.randint(1000,9999),random.randint(1000,9999)]) # tri avec affichage du temps de tri tps=time.clock() trirapidesousliste(L) print time.clock()-tps # vérification que le tri est correct et affichage d'éventuelles erreurs for i in xrange(1,nmax): if L[i][1]<L[i-1][1]: print "erreur index ",i, L[i][1] # affichage de la liste triée for i in xrange(1,nmax): print L[i]
Prenons le cas d'un objet Python défini avec une classe:
class Monobjet(object): def __init__(self): self.x1 = None self.x2 = None self.x3 = None self.x4 = None
On va avoir une liste de tels objets (des instances de cette classe), et on va la trier, par exemple, selon la valeur de x2.
Comme pour le cas précédent, examinons les modifications à faire:
Voilà le code modifié:
#!/usr/bin/python # -*- coding: utf-8 -*- def trirapideobjets(L): def trirap(L, g, d): pivot = L[(g+d)//2].x2 i = g j = d while True: while L[i].x2<pivot: i+=1 while L[j].x2>pivot: j-=1 if i>j: break if i<j: L[i], L[j] = L[j], L[i] i+=1 j-=1 if g<j: trirap(L,g,j) if i<d: trirap(L,i,d) g=0 d=len(L)-1 trirap(L,g,d)
Ce code est bien entendu devenu spécifique au tri d'une liste d'objet de la classe Monobjet, classé selon x2.
Voilà le code pour le vérifier:
import random import time # fabrication d'une liste de 1000 objets de 4 valeurs aléatoires L=[] nmax=1000 for i in xrange(0,nmax): a=Monobjet() a.x1=random.randint(1000,9999) a.x2=random.randint(1000,9999) a.x3=random.randint(1000,9999) a.x4=random.randint(1000,9999) L.append(a) # tri avec affichage du temps de tri tps=time.clock() trirapideobjets(L) print time.clock()-tps # vérification que le tri est correct et affichage d'éventuelles erreurs for i in xrange(1,nmax): if L[i].x2<L[i-1].x2: print "erreur index ",i, L[i].x2 # affichage de la liste triée for i in xrange(1,nmax): print L[i].x1, L[i].x2, L[i].x3, L[i].x4
Rien ne vous empêche de généraliser, et de préparer une fonction de tri plus facile à adapter. Dans le code qui suit, la fonction tri n'est plus modifiée dans les adaptations, seules les 4 premières fonctions doivent m'être.
Dans cet exemple qui doit servir de modèle, les 4 fonctions ont été adaptées à un tri simple:
#!/usr/bin/python # -*- coding: utf-8 -*- def trirap_defpivot(L,k1,k2): return L[(k1+k2)//2] def trirap_cmpinf(L,k,pivot): return L[k]<pivot def trirap_cmpsup(L,k,pivot): return L[k]>pivot def trirap_action(L,k1,k2): L[k1], L[k2] = L[k2], L[k1] def trirapidegeneral(L): def trirap(L, g, d): pivot = trirap_defpivot(L,g,d) i = g j = d while True: while trirap_cmpinf(L,i,pivot): i+=1 while trirap_cmpsup(L,j,pivot): j-=1 if i>j: break if i<j: trirap_action(L,i,j) i+=1 j-=1 if g<j: trirap(L,g,j) if i<d: trirap(L,i,d) g=0 d=len(L)-1 trirap(L,g,d)
Et voilà le code pour vérifier:
import random import time # fabrication d'une liste de 1000 valeurs aléatoires L=[] nmax=1000 for i in xrange(0,nmax): L.append(random.randint(1000,9999)) # à décommenter pour vérifier l'efficacité avec une liste déjà triée #L.sort() # à décommenter en plus de L.sort() pour une liste triée à l'envers #L.reverse() # tri avec affichage du temps de tri tps=time.clock() trirapidegeneral(L) print time.clock()-tps # vérification que le tri est correct et affichage d'éventuelles erreurs for i in xrange(1,nmax): if L[i]<L[i-1]: print "erreur index ",i, L[i] # affichage de la liste triée for i in xrange(1,nmax): print L[i],
A titre d'entraînement, modifiez les 4 fonctions à adapter pour les différentes cas étudiés sur cette page: tri indexé, tri d'une liste de liste et tri d'une liste d'objets quelconques.
Amusez-vous bien!