Mis à jour le vendredi 17 novembre 2017
  • 40 heures
  • Difficile

Ce cours est visible gratuitement en ligne.

Ce cours existe en livre papier.

Vous pouvez obtenir un certificat de réussite à l'issue de ce cours.

Vous pouvez être accompagné et mentoré par un professeur particulier par visioconférence sur ce cours.

J'ai tout compris !

Parenthèse sur le tri en Python

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Trier une liste d'informations quelconque peut s'avérer très utile... et souvent difficile. Python nous offre plusieurs techniques pour trier, que ce soit de simples listes de nombres, de chaînes de caractères ou de données plus complexes (comme des objets dont nous avons créé nous-mêmes les classes).

Ce chapitre est une parenthèse : vous pouvez aller tout de suite au chapitre suivant sans problème, et revenir à celui-ci plus tard.

Première approche du tri

La première question que vous devriez vous poser : on a une liste, on veut la trier, mais que veut-on dire par « trier » ?

Trier, c'est ordonner la liste d'une façon cohérente. Par exemple, on pourrait vouloir trier une liste de noms par ordre alphabétique. Ou on pourrait vouloir trier une liste de nombres du plus petit au plus grand.

Dans tous les cas, trier une liste c'est la réordonner (changer son ordre, si nécessaire) selon certains critères. Il est important que vous gardiez en tête cette notion de « critères » par la suite, car nous allons en reparler.

Deux méthodes

Pour trier une séquence de données, Python nous propose deux méthodes :

  1. La première est une méthode de liste. Elle s'appelle tout simplement sort (trier en anglais). Elle travaille sur la liste-même et change donc son ordre, si c'est nécessaire.

  2. La seconde est la fonction sorted. Il s'agit d'une fonction builtin, c'est-à-dire qu'elle est disponible d'office dans Python sans avoir besoin d'importer quoique ce soit. Contrairement à la méthode sort de la class list, sorted travaille sur n'importe quel type de séquence (tuple, liste ou même dictionnaire). Une importante différence avec la méthode list.sort est qu'elle ne modifie pas l'objet d'origine, mais en retourne un nouveau.

Voyons quelques exemples :

>>> prenoms = ["Jacques", "Laure", "André", "Victoire", "Albert", "Sophie"]
>>> prenoms.sort()
>>> prenoms
['Albert', 'André', 'Jacques', 'Laure', 'Sophie', 'Victoire']
>>> # Et avec la fonction 'sorted'
... prenoms = ["Jacques", "Laure", "André", "Victoire", "Albert", "Sophie"]
>>> sorted(prenoms)
['Albert', 'André', 'Jacques', 'Laure', 'Sophie', 'Victoire']
>>> prenoms
['Jacques', 'Laure', 'André', 'Victoire', 'Albert', 'Sophie']
>>>

Vous devriez remarquer deux choses ici :

  1. D'abord, Python a trié notre liste par ordre alphabétique. Nous verrons plus tard pourquoi.

  2. Le second moyen (avec la fonction sorted) n'a pas modifié la liste, elle a juste retournée une nouvelle liste triée. La méthode de liste sort, elle, a travaillée sur notre liste et l'a modifiée.

Aperçu des critères de tri

Python a trié la liste par ordre alphabétique... mais nous ne lui avons rien demandé à cet égard. En un sens, tant mieux, si c'est ce que vous vouliez faire, mais il est préférable de comprendre pourquoi. Je vous met ici un petit code qui devrait vous aider à comprendre sur quelle information Python se fonde pour déterminer la meilleure méthode de tri :

>>> sorted([1, 8, -2, 15, 9])
[-2, 1, 8, 9, 15]
>>> sorted(["1", "8", "-2", "15", "9"])
['-2', '1', '15', '8', '9']
>>>

La réponse se trouve dans la différence entre la ligne 1 et la ligne 3. Vous avez trouvé ?

Pour Python, la méthode de tri dépend du type des éléments que la séquence contient. On lui a demandé de trier une liste de nombres (type int) et Python trie du plus petit au plus grand. Sans surprise.

À la ligne 3 cependant, on lui demande de trier la même liste, sauf que nos nombres sont devenus des chaînes de caractères (type str). Python choisit donc de trier la liste par ordre alphabétique.

Et si on a une liste contenant plusieurs types ?

Dans ce cas, Python va vous dire, à sa façon, qu'il ne sait pas quelle méthode de tri choisir.

>>> sorted([1, "8", "-2", "15", 9])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unorderable types: str() < int()
>>>

Notre liste contient des nombres (type int) et des chaînes de caractères (type str). Le message d'erreur n'est peut-être pas très explicite tant qu'on ne connaît pas la façon dont Python trie une séquence, nous verrons ça un peu plus loin dans le chapitre.

En attendant, intéressons-nous à des types plus particuliers !

Trier avec des clés précises

Les deux moyens que nous venons de voir sont pratiques, mais limités. Si nous voulons trier une liste contenant des données de types différents, selon des critères un peu plus particuliers, on va avoir quelques problèmes.

Considérez cet exemple : on veut conserver, dans une liste simple, les étudiants, leur âge et leur note moyenne (entre 0 et 20). On va commencer par créer une liste assez simple, contenant des tuples. Pour chaque tuple, on indiquera le nom de l'étudiant, son âge et sa moyenne. Voyons le code :

etudiants = [
    ("Clément", 14, 16),
    ("Charles", 12, 15),
    ("Oriane", 14, 18),
    ("Thomas", 11, 12),
    ("Damien", 12, 15),
]

Souvenez-vous : première colonne, prénom, deuxième colonne, âge et troisième colonne, moyenne entre 0 et 20.

Maintenant, si vous essayez de trier cette liste sans préciser de méthode :

>>> sorted(etudiants)
[
    ('Charles', 12, 15),
    ('Clément', 14, 16),
    ('Damien', 12, 15),
    ('Oriane', 14, 18),
    ('Thomas', 11, 12)
]
>>>

Le plus important pour nous, c'est que le tri semble s'effectuer sur la première colonne : sur les prénoms. L'ordre retourné est celui des étudiants par ordre alphabétique.

Maintenant, supposons que nous voulions trier par note.

Il suffit de changer les colonnes de notre liste, non ?

Oui, c'est une solution et il s'agit probablement de la solution à laquelle on pense le plus vite : changer les colonnes de notre liste, pour mettre les notes au début de notre tuple, et après trier la liste.

Mais il y a plus simple !

L'argument key

La méthode list.sort ou la fonction sorted ont tous deux un paramètre optionnel, appelé key.

Cet argument attend... une fonction. Attendez ! Je m'explique.

La fonction à passer en paramètre prend un élément de la liste et retourne ce sur quoi doit s'effectuer le tri.

Donc la première chose est de créer une fonction ?

Oui, mais de façon assez simple : nous allons utiliser nos fonctions lambdas. Vous vous en souvenez ? Je vous donne un petit exemple de code si besoin :

>>> doubler = lambda x: x * 2
>>> doubler
<function <lambda> at 0x00000000029AD1E0>
>>> doubler(8)
16
>>>

Les fonctions lambdas sont des fonctions particulières que l'on peut créer grâce au mot clélambda.

Sa syntaxe est la suivante :

  1. D'abord, après le mot clé lambda, les arguments de la fonction à créer, séparés par une virgule si il y en a plusieurs ;

  2. Ensuite, les deux points (:) ;

  3. Et ensuite le retour de la fonction. Ici, on retourne le paramètre fois 2, tout simplement.

Pourquoi ce rappel sur les lambdas ?

Parce que, pour trier, nous allons nous en servir. Pour préciser la méthode de tri, il nous faut une fonction qui prenne en paramètre un élément de la liste à trier et retourne l'élément qui doit être utilisé pour trier.

  • L'élément de notre liste etudiants, c'est un tuple contenant le prénom, l'âge et la moyenne de l'étudiant ;

  • On veut trier le tableau des étudiants en fonction des notes (la troisième colonne du tuple).

Est-ce que ces informations vous aident pour créer notre fonction lambda ?

La voici :

lambda colonnes: colonnes[2]

colonnes contiendra un élément de la liste des étudiants (c'est-à-dire un tuple). Si on retournecolonnes[2], cela signifie qu'on veut récupérer la moyenne de l'étudiant (troisième colonne). Souvenez-vous, pour un tuple, la première colonne est toujours 0.

Essayons à présent de trier notre liste d'étudiants en fonction de leur moyenne :

>>> sorted(etudiants, key=lambda colonnes: colonnes[2])
[
    ('Thomas', 11, 12), 
    ('Charles', 12, 15), 
    ('Damien', 12, 15), 
    ('Clément', 14, 16),
    ('Oriane', 14, 18)
]
>>>

Si le code ne vous paraît pas clair, prenez le temps de relire les explications. Il faut un peu de temps pour s'adapter aux fonctions lambdas, mais vous verrez qu'elles sont parfois très utiles.

Trier une liste d'objets

Jusqu'ici, nous avons trié des listes contenant des nombres ou chaînes de caractères. Ce sont des objets, bien entendu, mais maintenant je voudrais vous montrer comment trier des objets issus de classes que nous avons créées.

Je vais reprendre le même exemple de notre tableau d'étudiants. Simplement, au lieu de conserver des tuples, nous allons conserver des objets. Plus intuitif et plus lisible, je trouve :

class Etudiant:

    """Classe représentant un étudiant.

    On représente un étudiant par son prénom (attribut prenom), son âge
    (attribut age) et sa note moyenne (attribut moyenne, entre 0 et 20).

    Paramètres du constructeur :
        prenom -- le prénom de l'étudiant
        age -- l'âge de l'étudiant
        moyenne -- la moyenne de l'étudiant

    """

    def __init__(self, prenom, age, moyenne):
        self.prenom = prenom
        self.age = age
        self.moyenne = moyenne

    def __repr__(self):
        return "<Étudiant {} (âge={}, moyenne={})>".format(
                self.prenom, self.age, self.moyenne)

Maintenant, recréons notre liste :

etudiants = [
    Etudiant("Clément", 14, 16),
    Etudiant("Charles", 12, 15),
    Etudiant("Oriane", 14, 18),
    Etudiant("Thomas", 11, 12),
    Etudiant("Damien", 12, 15),
]

Si vous essayez de trier notre liste telle quelle, vous allez avoir une erreur qui devrait vous sembler familière :

>>> etudiants
[
    <Étudiant Clément (âge=14, moyenne=16)>,
    <Étudiant Charles (âge=12, moyenne=15)>,
    <Étudiant Oriane (âge=14, moyenne=18)>,
    <Étudiant Thomas (âge=11, moyenne=12)>,
    <Étudiant Damien (âge=12, moyenne=15)>
]
>>> sorted(etudiants)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unorderable types: Etudiant() < Etudiant()
>>>

Python ne sait pas comment trier nos étudiants. Il y a deux façons de le lui expliquer :

  1. L'une est de définir la méthode spéciale __lt__ de notre classe. C'est en effet cette méthode (utilisée pour la comparaison) qui est utilisée par Python pour trier une liste, en comparant chacun de ses éléments. La méthode __lt__ (lower than) correspond à l'opérateur < ;

  2. On peut aussi utiliser l'argument key, comme nous l'avons fait précédemment.

Ici notre seconde possibilité est plus pertinente. Redéfinir la méthode __lt__ est une bonne idée si notre objet est un nombre (par exemple une durée ou bien une heure). Dans ce cas précis, il est préférable d'utiliser l'argument key de la fonction sorted (ou de la méthode list.sort).

Saurez-vous trier cette liste d'étudiants en fonction de leur moyenne ?

Voici le code :

>>> sorted(etudiants, key=lambda etudiant: etudiant.moyenne)
[
    <Étudiant Thomas (âge=11, moyenne=12)>,
    <Étudiant Charles (âge=12, moyenne=15)>,
    <Étudiant Damien (âge=12, moyenne=15)>,
    <Étudiant Clément (âge=14, moyenne=16)>,
    <Étudiant Oriane (âge=14, moyenne=18)>
]
>>>

On obtient la même chose que dans notre exercice précédent, quand nous utilisions des tuples. Je trouve personnellement cette méthode plus lisible.

Trier dans l'ordre inverse

Il arrive souvent que l'on veuille trier dans l'ordre inverse. Par exemple, que l'on veuille trier nos étudiants par ordre inverse d'âge (du plus grand au plus petit).

Une solution est de trier et ensuite d'inverser la liste, mais là encore, il existe plus rapide : l'argument reverse.

C'est un argument booléen que l'on peut passer à la méthode de liste sort ou à la fonction sorted.

Essayons par exemple de trier nos étudiants par ordre inverse d'âge :

>>> sorted(etudiants, key=lambda etudiant: etudiant.age, reverse=True)
[
    <Étudiant Clément (âge=14, moyenne=16)>,
    <Étudiant Oriane (âge=14, moyenne=18)>,
    <Étudiant Charles (âge=12, moyenne=15)>,
    <Étudiant Damien (âge=12, moyenne=15)>,
    <Étudiant Thomas (âge=11, moyenne=12)>
]
>>>

Plutôt simple, n'est-ce pas ? ;)

Plus rapide et plus efficace

Les méthodes de tri que nous avons vues jusqu'ici sont très pratiques. Leur plus grand inconvénient est de reposer sur des fonctions lambdas. Il est vrai que définir une lambda est rapide (et, une fois qu'on s'est habitué à la syntaxe, assez lisible). Par contre les fonctions lambdas ne sont pas le meilleur choix au niveau rapidité, si vous voulez trier une liste contenant beaucoup d'objets.

Mais tu as dit que le paramètre key attendait une fonction, ne peut-on définir une fonction « ordinaire » ?

Si si. C'est tout à fait possible. Mais la plupart du temps, une des fonctions du module operator que nous allons voir fait très bien le travail.

Les fonctions du module operator

Le module operator propose plusieurs fonctions qui vont s'avérer utiles pour nous, dans ce cas précis. Nous allons nous intéresser tout particulièrement aux fonctions itemgetter et attrgetter, mais sachez qu'il en existe d'autres et que le module operator n'est pas uniquement utile pour le tri, loin s'en faut.

Trier une liste de tuples

D'abord, voyons notre exemple avec les tuples :

etudiants = [
    ("Clément", 14, 16),
    ("Charles", 12, 15),
    ("Oriane", 14, 18),
    ("Thomas", 11, 12),
    ("Damien", 12, 15),
]

Si on veut trier par moyenne ascendante, nous avons vu qu'il suffisait de faire :

sorted(etudiants, key=lambda etudiant: etudiant[2])

Pour faire la même chose sans fonction lambda, avec la fonction itemgetter du module operator :

from operator import itemgetter
sorted(etudiants, key=itemgetter(2))

On appelle la fonction itemgetter avec le paramètre 2. Un objet operator.itemgetter est créé et passé au paramètre key de la fonction sorted. Ensuite, pour chaque étudiant contenu dans notre liste, l'objet operator.itemgetter est appelé et retourne la note moyenne de l'étudiant.

Au final, on obtient le même résultat qu'avec notre fonction lambda, mais cette méthode est plus rapide sur un grand nombre de données et, une fois qu'on s'est habitué à son aspect, plus facile à lire.

Trier une liste d'objets

On peut faire la même chose si on parcourt une liste d'objets, mais cette fois, on utilise la fonction attrgetter. Je vous remet le code pour être sûr que vous avez le même que moi :

class Etudiant:

    """Classe représentant un étudiant.

    On représente un étudiant par son prénom (attribut prenom), son âge
    (attribut age) et sa note moyenne (attribut moyenne, entre 0 et 20).

    Paramètres du constructeur :
        prenom -- le prénom de l'étudiant
        age -- l'âge de l'étudiant
        moyenne -- la moyenne de l'étudiant

    """

    def __init__(self, prenom, age, moyenne):
        self.prenom = prenom
        self.age = age
        self.moyenne = moyenne

    def __repr__(self):
        return "<Étudiant {} (âge={}, moyenne={})>".format(
                self.prenom, self.age, self.moyenne)

etudiants = [
    Etudiant("Clément", 14, 16),
    Etudiant("Charles", 12, 15),
    Etudiant("Oriane", 14, 18),
    Etudiant("Thomas", 11, 12),
    Etudiant("Damien", 12, 15),
]

Et maintenant pour trier notre liste d'étudiants par note moyenne ascendante :

from operator import attrgetter
sorted(etudiants, key=attrgetter("moyenne"))

Le système est le même, sauf que l'on travaille ici sur une liste d'objets et que le calcul est fait sur un attribut de l'objet (ici "moyenne") au lieu d'un tuple.

Trier selon plusieurs critères

Trier selon un critère, c'est déjà très bien, mais trier selon plusieurs critères, ce peut être encore mieux. Si nous voulons, disons, trier nos étudiants par âge et note moyenne. C'est-à-dire que le tri se fera par âge, mais si deux étudiants ont le même âge, le tri se fera sur leur moyenne.

La bonne nouvelle ? Rien de nouveau : passez juste un nouveau paramètre à la fonction attrgetter :

>>> sorted(etudiants, key=attrgetter("age", "moyenne"))
[
    <Étudiant Thomas (âge=11, moyenne=12)>,
    <Étudiant Charles (âge=12, moyenne=15)>,
    <Étudiant Damien (âge=12, moyenne=15)>,
    <Étudiant Clément (âge=14, moyenne=16)>,
    <Étudiant Oriane (âge=14, moyenne=18)>
]
>>>

Vous avez peut-être remarqué que l'ordre de Charles et Damien dans la liste est identique à avant, même si d'autres étudiants ont changé de place : en effet, Charles et Damien ont le même âge et la même moyenne et leur ordre n'est pas modifié par Python.

Cette propriété est appelée « stabilité ». Si deux éléments de la séquence à comparer sont identiques, leur ordre est conservé.

Cette propriété du tri en Python permet de chaîner nos tris.

Chaînage de tris

Pour vous montrer un exemple concret, nous allons changer d'objets : nous allons travailler sur un inventaire de produits avec leur prix et quantité vendues.

class LigneInventaire:

    """Classe représentant une ligne d'un inventaire de vente.

    Attributs attendus par le constructeur :
        produit -- le nom du produit
        prix -- le prix unitaire du produit
        quantite -- la quantité vendue du produit.

    """

    def __init__(self, produit, prix, quantite):
        self.produit = produit
        self.prix = prix
        self.quantite = quantite

    def __repr__(self):
        return "<Ligne d'inventaire {} ({}X{})>".format(
                self.produit, self.prix, self.quantite)

# Création de l'inventaire
inventaire = [
    LigneInventaire("pomme rouge", 1.2, 19),
    LigneInventaire("orange", 1.4, 24),
    LigneInventaire("banane", 0.9, 21),
    LigneInventaire("poire", 1.2, 24),
]

On veut trier cette liste par prix et par quantité. Facile, c'est ce qu'on a fait un peu plus haut :

from operator import attrgetter
sorted(inventaire, key=attrgetter("prix", "quantite"))

Ce qui vous renvoie :

[
    <Ligne d'inventaire banane (0.9X21)>,
    <Ligne d'inventaire pomme rouge (1.2X19)>,
    <Ligne d'inventaire poire (1.2X24)>,
    <Ligne d'inventaire orange (1.4X24)>
]

Mais si vous voulez trier par prix croissant et par quantité décroissante ? C'est-à-dire qu'on veut trier par prix croissant, mais que si deux lignes d'inventaires ont le même prix, alors on trie dans l'ordre décroissant de quantité ?

Le plus simple ici est de faire deux tris en utilisant la propriété de stabilité. La subtilité, c'est que l'on va trier d'abord par notre second critère et ensuite par notre premier. Ici, nous allons donc trier d'abord par ordre décroissant de quantité, puis ensuite par ordre croissant de prix.

Si vous vous demandez pourquoi, faites plusieurs essais (dans l'ordre que j'ai indiqué et dans l'ordre inverse). Si cela vous aide, essayez d'écrire l'inventaire sur une feuille et de trier dans un ordre et dans l'autre.

Voici le code pour notre tri. D'abord par quantité, ensuite par prix :

inventaire.sort(key=attrgetter("quantite"), reverse=True)
sorted(inventaire, key=attrgetter("prix"))

Et vous devriez obtenir :

[
    <Ligne d'inventaire banane (0.9X21)>,
    <Ligne d'inventaire poire (1.2X24)>,
    <Ligne d'inventaire pomme rouge (1.2X19)>,
    <Ligne d'inventaire orange (1.4X24)>
]

On utilise ici la méthode de liste sort comme on aurait pu utiliser la fonction sorted.

Regardez surtout l'ordre dans lequel la poire et la pomme rouge apparaissent : les deux lignes d'inventaire ont le même prix, mais puisque la poire a été vendue en plus grande quantité, elle apparaît en premier. Ceci n'aurait pas été possible sans la stabilité dans le tri.

Sans cette propriété, le second tri (par prix) aurait complètement modifié l'ordre de notre liste, rendant inutile notre premier tri (par quantité inverse).

Voilà pour ce tour d'horizon des méthodes de tri proposées par Python. Sachez que vous pourrez retrouver les fonctions clés (souvent en paramètre key d'une fonction) pour d'autres usages que le tri.

En résumé

  • Le tri en Python se fait grâce à la méthode de liste sort, qui modifie la liste d'origine, et la fonction sorted, qui ne modifie pas la liste (ou la séquence) passée en paramètre ;

  • On peut spécifier des fonctions clés grâce à l'argument key. Ces fonctions sont appelées pour chaque élément de la séquence à trier, et retournent le critère du tri ;

  • Le module operator propose les fonctions itemgetter et attrgetter qui peuvent être très utiles en tant que fonction clés, si on veut trier une liste de tuples ou une liste d'objets selon un attribut ;

  • Le tri en Python est « stable », c'est-à-dire que l'ordre de deux éléments dans la liste n'est pas modifié s'ils sont égaux. Cette propriété permet le chaînage de tri.

Exemple de certificat de réussite
Exemple de certificat de réussite