Outils pour utilisateurs

Outils du site


tri_rapide

Ceci est une ancienne révision du document !


Tri rapide ("quicksort") de liste d'objets complexes, 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à 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

Tri rapide d'une liste d'objets simples (chaînes de caractères, nombres, ...)

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:

  • listes de 1000 éléments: 0.004 seconde
  • listes de 10000 éléments: 0.05 seconde
  • listes de 100000 éléments: 0.6 seconde
  • listes de 1000000 éléments: 8 secondes

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:

  • listes déjà triées: 0.03 seconde
  • listes déjà triées à l'envers: 0.03 seconde

Tri rapide de listes d'objets simples sans modification de la liste donnée

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)

Tri rapide 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 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:

  • au lieu de chercher le pivot L[(g+d)//2], on va chercher le pivot L[X[(g+d)//2]]
  • au lieu de comparer L[i]<pivot, on va comparer L[X[i]]<pivot
  • au lieu de comparer L[j]>pivot, on va comparer L[X[j]]>pivot
  • au lieu d'échanger L[i] et L[j], on va échanger seulement leurs index X[i] et X[j]

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],

Tri rapide d'objets complexes

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:

Tri rapide de listes de listes

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:

  • le pivot cherché sera: pivot = L[(g+d)//2][1]
  • la 1ère comparaison sera: L[i][1]<pivot
  • la 2ème comparaison sera: L[j][1]>pivot
  • et les échanges ne seront pas modifiées

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]

Tri rapide de listes d'objets quelconques

Prenons le cas d'un objet Python défini avec une classe:

class Monobjet(objet):
    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:

  • pour la recherche du pivot, on aura: pivot = L[(g+d)//2].x2
  • pour la 1ère comparaison, on aura: L[i].x2<pivot
  • pour la 2ème comparaison, on aura: L[j].x2>pivot
  • et la ligne d'échange ne changera pas.

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

Tri rapide généralisé de listes d'objets quelconques

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!

tri_rapide.1210046500.txt.gz · Dernière modification: 2008/05/06 06:01 de tyrtamos

Outils de la page