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à celle que j'utilise.
Le tri par insertion n'est pas réputé pour être le tri le plus rapide, mais il est très simple à comprendre, et donc plus facile à adapter à ce qu'on veut. En plus, il n'est pas récursif, ce qui est mieux pour Python.
Le principe est simple: on pointe successivement sur tous les membres de la liste à partir du 2ème (boucle for i), et pour chaque membre, on l'insère au bon endroit des membres précédents (boucle for k) dans l'ordre de tri.
Voilà ce que ça donne comme code:
#!/usr/bin/python # -*- coding: utf-8 -*- def triinsertion(L): for i in xrange(1,len(L)): if L[i]<L[i-1]: for k in xrange(0,i): if L[i]<L[k]: X=L.pop(i) L.insert(k,X) break
Le tri par insertion est sanctionné dans sa rapidité par le fait qu'il est obligé de tester chaque valeur avec statistiquement la moitié des valeurs précédentes.
On va diminuer fortement la quantité de ces tests en cherchant l'emplacement d'insertion par dichotomie!
Commençons par mettre au point une fonction de recherche par dichotomie.
Pour comprendre ce qu'est la dichotomie, je vous propose une petite expérience: chercher un mot dans un gros dictionnaire papier:
A chaque fois que vous progressez, le nombre de pages qui reste est divisé par 2.
Ainsi, dans un dictionnaire de 1024 pages, vous êtes certain de trouver votre page en 10 recherches seulement (et pas en 512), puisque 1024/2**10=1.
Voilà le code de recherche par dichotomie:
#!/usr/bin/python # -*- coding: utf-8 -*- def dichot(L,i,j,X): if X>L[j]: return j+1 while i!=j: k=(i+j)//2 if X<=L[k]: j=k else: i=k+1 return i
Code de test:
L=[2,3,4,5,7] print dichot(L,0,4,1) # doit donner 0 print dichot(L,0,4,2) # doit donner 0 print dichot(L,0,4,3) # doit donner 1 print dichot(L,0,4,4) # doit donner 2 print dichot(L,0,4,5) # doit donner 3 print dichot(L,0,4,6) # doit donner 4 print dichot(L,0,4,7) # doit donner 4 print dichot(L,0,4,8) # doit donner 5
Avec k=dichot(L,i,j,X):
Maintenant qu'on a un bon code de recherche par dichotomie, on va modifier notre algorithme de tri pour l'utiliser:
#!/usr/bin/python # -*- coding: utf-8 -*- def dichot(L,i,j,X): if X>L[j]: return j+1 while i!=j: k=(i+j)//2 if X<=L[k]: j=k else: i=k+1 return i def triinsertion(L): for i in xrange(1,len(L)): if L[i]<L[i-1]: k=dichot(L,0,i-1,L[i]) X=L.pop(i) L.insert(k,X)
On peut même faire un code plus compact qui intègre la recherche par dichotomie à l'intérieur de la fonction de tri: c'est ma meilleure proposition.
#!/usr/bin/python # -*- coding: utf-8 -*- def triinsertion(L): def dichot(L,i,j,X): while i!=j: k=(i+j)//2 if X<=L[k]: j=k else: i=k+1 return i for i in xrange(1,len(L)): if L[i]<L[i-1]: k=dichot(L,0,i-1,L[i]) X=L.pop(i) L.insert(k,X)
Et voilà le code pour le vérifier:
#!/usr/bin/python # -*- coding: utf-8 -*- import random import time # fabrication d'une liste de 1000 valeurs aléatoires L=[] for i in xrange(0,1000): 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() triinsertion(L) print time.clock()-tps # vérification que le tri est correct et affichage d'éventuelles erreurs for i in xrange(1,1000): if L[i]<L[i-1]: print "erreur index ",i, L[i] # affichage de la liste triée for i in xrange(1,1000): print L[i],
Efficacité de la fonction de tri proposée avec des listes de nombres de 4 chiffres:
Ce qui n'est pas mal du tout pour un algorithme de tri interprété
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.
On va donc créer cette liste d'index R de la façon suivante:
# liste d'index R pour une liste L donnée R=[] for i in xrange(0,len(L)): R.append(i)
Quand on a cette liste d'index:
Voilà le nouveau code de tri indexé:
#!/usr/bin/python # -*- coding: utf-8 -*- def triinsertionindex(L,R): def dichot(L,i,j,X,R): while i!=j: k=(i+j)//2 if X<=L[R[k]]: j=k else: i=k+1 return i for i in xrange(1,len(L)): if L[R[i]]<L[R[i-1]]: k=dichot(L,0,i-1,L[R[i]],R) X=R.pop(i) R.insert(k,X)
Et volà le code de test:
import random import time # fabrication d'une liste de 1000 valeurs aléatoires L=[] for i in xrange(0,1000): 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() # fabrication d'une liste d'index R=[] for i in xrange(0,1000): R.append(i) # tri indexé avec affichage du temps de tri tps=time.clock() triinsertionindex(L,R) print time.clock()-tps # vérification que le tri est correct et affichage d'éventuelles erreurs for i in xrange(1,1000): if L[R[i]]<L[R[i-1]]: print "erreur index ",i, L[R[i]] # affichage de la liste triée for i in xrange(1,1000): print L[R[i]],
La rapidité de ce tri indexé est à peu près la même que celle du tri précédent.
Comme je l'ai dit au début, l'avantage d'avoir sous la main un bon algorithme de tri dont vous connaissez le code, c'est que vous pouvez l'adapter facilement pour traiter des cas où la fonction sort() de Python est insuffisante.
Amusez-vous bien!