Trier des mots avec Python, c'est facile, mais l'ordre que vous obtenez n'est pas en général celui d'un dictionnaire français, mais celui de la police de caractères utilisée. Par exemple, la majuscule “X” se trouve avant la minuscule “a”. Quand aux caractères accentués, ils se trouvent derrière les minuscules non accentuées: 'à' est donc après 'x'…

Il existe une méthode de base intégrée à Python pour faire ça. Je propose ici une adaptation un peu complétée qui répond à tous les cas que j'ai pu tester. Pour ces cas, j'ai pris comme référence l'excellent article suivant, qui traite des règles de tri des dictionnaires français (et un grand merci à nos cousins canadiens ):

• http://www-clips.imag.fr/geta/gilles.serasset/tri-du-francais.html

on va créer une méthode de comparaison qui pourra être utilisée dans les arguments de la méthode sort:

import locale
 
class Compfr(object):
 
    def __init__(self, decod='utf-8'):
        self.decod = decod
        locale.setlocale(locale.LC_ALL, '')
        self.espinsec = u'\xA0' # espace insécable
 
    def __call__(self, v1, v2):
 
        # on convertit en unicode si nécessaire
        if isinstance(v1, str):
            v1 = v1.decode(self.decod)
        if isinstance(v2, str):
            v2 = v2.decode(self.decod)
 
        # on retire les tirets et les blancs insécables
        v1 = v1.replace(u'-', u'')
        v1 = v1.replace(self.espinsec, u'')
        v2 = v2.replace(u'-', '')
        v2 = v2.replace(self.espinsec, u'')
 
        # on retourne le résultat de la comparaison
        return locale.strcoll(v1, v2)

Et voilà comment on va l'utiliser:

L = ['pèche', 'PÈCHE', 'pêche', 'PÊCHE', 'péché', 'PÉCHÉ', 'pécher', 'pêcher']
compfr = Compfr()
L.sort(cmp=compfr)
for mot in L:
    print mot

Ce qui donne à l'exécution (et qui est l'ordre correct):

pèche
PÈCHE
pêche
PÊCHE
péché
PÉCHÉ
pécher
pêcher

Si on est dans Python 3.x, l'argument cmp de sort() n'existe plus, mais grâce à cmp_to_key du module functools, on peut encore utiliser la même méthode de comparaison avec l'argument 'key'. Il suffira d'écrire: L.sort(key=cmp_to_key(compfr)) après avoir importé le module functools.

Tel que la classe Compfr() est définie, la liste est supposée être composée de mots encodés soit en unicode, soit en 'utf-8'. Si les mots non-unicode sont dans un autre encodage, on le donne à l'initialisation. Par exemple, si c'est 'cp1252' (=Windows), on écrit: compfr = Compfr('cp1252'). Dans tous les cas, les comparaisons sont faites en unicode.

Volà les listes utilisées pour les tests, issues de l'article de référence cité plus haut. Les mots se présentent déjà dans l'ordre correct, et le tri doit donc les renvoyer à l'identique.

L = [u'surélévation', u'sûrement', u'suréminent', u'sûreté']
L = [u'cote', u'côte', u'Côte', u'coté', u'Coté', u'côté', u'Côté', u'coter']
L = [u'élève', u'élevé']
L = [u'gène', u'gêne']
L = [u'MÂCON', u'maçon']
L = [u'pèche', u'PÈCHE', u'pêche', u'PÊCHE', u'péché', u'PÉCHÉ', u'pécher', u'pêcher']
L = [u'relève', u'relevé', u'révèle', u'révélé']
L = [u'cadurcien', u'cæcum', u'caennais', u'cæsium', u'cafard', u'coercitif', u'cœur']
L = [u'vice-consul', u'vicennal', u'vice-président', u'vice-roi', u'vicésimal', u'vice' + u'\xA0' + u'versa', u'vice-versa']

NB: u'\xA0' est l'espace insécable.

Il suffit d'adapter la fonction de recherche par dichotomie pour qu'elle accepte d'utiliser la méthode de comparaison “compfr(v1,v2)” définie ci-dessus. On peut y ajouter, si nécessaire, une fonction affectée à key pour corriger chaque donnée avant la comparaison.

def dichot(x, L, comp=cmp, key=None):
    i, j = 0, len(L)-1
    if key == None:
        key = lambda c: c
    x = key(x)
    if comp(x,key(L[j]))>0:
        return [1,j]
    while i!=j:
        k=(i+j)//2
        if comp(x,key(L[k]))<1:
            j = k
        else:
            i = k+1
    if comp(x,key(L[i]))==0:
        return [0, i]
    return [-1, i]

Dans cette fonction, les paramètres en entrée sont les suivants:

• x = chaîne à rechercher
• L = liste triée
• cmp = fonction de comparaison à utiliser (qui doit être la même que celle qui a servi au tri!)
• key = fonction de conversion utile à ce qu'on recherche

Cette fonction renvoie une liste de 2 valeurs:

• la 1ère est le critère de réussite
• la 2ème est l'indice dans la liste.

Le critère de réussite est analogue au résultat de la fonction intégrée cmp(v1,v2): <0 si v1<v2; >0 si v1>v2; et =0 si v1==v2

• Si la valeur x est trouvée dans la liste L, la fonction renvoie [0,i], i étant l'indice de la valeur trouvée dans L.

• Si la valeur x ne se trouve pas dans la liste L:
  • si [-1,0] ⇒ la valeur cherchée x est inférieure à la valeur la plus petite de la liste
  • si [-1,i] avec i>0 ⇒ la valeur cherchée x se trouve entre la valeur d'indice i-1 et celle d'indice i
  • si [1,i] avec i==len(L)-1 ⇒ la valeur cherchée x est supérieure à la valeur la plus grande de la liste

En cas de doublon dans la liste:

• si on cherche le doublon et qu'on le trouve, on trouve celui d'indice le plus faible
• si on cherche une valeur juste inférieure au doublon, on trouve aussi le doublon d'indice le plus faible

Amusez-vous bien!