Outils pour utilisateurs

Outils du site


tri_insertion

Tris de listes par insertion, avec recherche par dichotomie, avec ou sans indexation

Problématique

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.

Tri par insertion

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

Tri par insertion avec recherche par dichotomie

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.

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:

  • vous l'ouvrez au milieu: le mot ne s'y trouve pas, mais il est avant.
  • vous ouvrez la moitié de la 1ère moitié: le mot ne s'y trouve pas, mais il est après.
  • vous ouvrez la moitié de la 2ème moitié,
  • etc…

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):

  • si X se trouve dans la liste, k=index de la valeur trouvée
  • si X ne s'y trouve pas:
    • si X est > dernière valeur, renvoie j+1
    • sinon, renvoie l'index k qui correspond à la 1ère valeur supérieure à la valeur cherchée.

Tri par insertion avec recherche par dichotomie

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:

  • tri de 1000 valeurs au hasard: 0.005 secondes
  • tri de 1000 valeurs déjà triées: 0.0002 secondes
  • tri de 1000 valeurs déjà triées à l'envers: 0.005 secondes
  • tri de 10000 valeurs au hasard: 0.17 secondes
  • tri de 10000 valeurs déjà triées: 0.0014 secondes
  • tri de 10000 valeurs déjà triées à l'envers: 0.2 secondes

Ce qui n'est pas mal du tout pour un algorithme de tri interprété

Tri indexé

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:

  • au lieu de comparer L[k1] et L[k2], on comparera L[R[k1]] et L[R[k2]]
  • au lieu de prendre la valeur X=L[k], on prendra la valeur X=L[R[k]]
  • au lieu de modifier la valeur L[k], on modifiera seulement son index R[k]
  • et à la fin, on trouvera la liste triée en prenant les L[R[i]] avec i de 0 à len(L)-1

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!

tri_insertion.txt · Dernière modification: 2008/05/05 11:24 par tyrtamos

Outils de la page