Trier une table

Introduction

Trier une table, c'est en réordonner les lignes selon une colonne (ou plusieurs). Cette opération courante a deux utilités principales : rendre les données lisibles pour un humain (classement alphabétique, palmarès) et préparer la table à d'autres opérations (recherche dichotomique, jointure ordonnée).

Imaginez une main de cartes qu'on aligne par valeur croissante, ou une liste de prénoms qu'on range par ordre alphabétique : trier, c'est exactement cela — mais à grande échelle et selon n'importe quel critère choisi.

[PD04] précise que vous pouvez utiliser une fonction de tri intégrée à la bibliothèque standard — pas besoin de réécrire un algorithme de tri. C'est ce que nous ferons avec la fonction sorted() de Python.

La fonction sorted()

sorted(iterable) renvoie une nouvelle liste contenant les éléments de l'itérable, triés par ordre croissant. C'est la version la plus simple :

nombres = [3, 1, 4, 1, 5, 9, 2, 6]
print(sorted(nombres))
# [1, 1, 2, 3, 4, 5, 6, 9]

Trier une table par une colonne

Sur une liste de dictionnaires, sorted() seul ne sait pas comparer — un dictionnaire {"nom": "Alice", ...} n'a pas d'ordre intrinsèque. Il faut indiquer selon quelle colonne trier, via le paramètre key=.

key= attend une fonction qui, appliquée à une ligne, retourne la valeur à utiliser pour la comparaison. On utilise pour cela une fonction lambda ou une fonction nommée :

eleves = [
    {"nom": "Chloé",   "age": 16, "classe": "1G2"},
    {"nom": "Alice",   "age": 16, "classe": "1G2"},
    {"nom": "Dimitri", "age": 17, "classe": "1G2"},
    {"nom": "Bob",     "age": 17, "classe": "1G3"},
]

# Tri par nom (ordre alphabétique)
par_nom = sorted(eleves, key=lambda e: e["nom"])

for e in par_nom:
    print(e["nom"])
# Alice
# Bob
# Chloé
# Dimitri

lambda e: e["nom"] est une mini-fonction sans nom, qu'on définit à la volée : appliquée à une ligne e, elle retourne e["nom"]. C'est elle qui sert de critère de comparaison.

Tri par colonne numérique

Trier par âge fonctionne exactement de la même façon, à condition que la colonne soit numérique :

Sortie :

16 Chloé
16 Alice
17 Dimitri
17 Bob

Tri descendant

Pour inverser l'ordre, ajouter reverse=True :

par_age_desc = sorted(eleves, key=lambda e: e["age"], reverse=True)

for e in par_age_desc:
    print(e["age"], e["nom"])
# 17 Dimitri
# 17 Bob
# 16 Chloé
# 16 Alice

Ordre stable

Une propriété essentielle de sorted() : c'est un tri stable. Cela signifie que les éléments ayant la même valeur de clé conservent leur ordre relatif d'origine. C'est l'équivalent d'un bibliothécaire qui range des livres par auteur sans bouleverser l'ordre des éditions dans chaque auteur.

Reprenez l'exemple précédent. Dans la table d'entrée, Chloé apparaît avant Alice. Après le tri par âge, Chloé et Alice ont toutes deux 16 ans — et le tri stable les place dans le même ordre que dans l'entrée : Chloé d'abord, puis Alice.

Tri par plusieurs critères

Tri par classe, puis par nom à l'intérieur de chaque classe :

# Méthode 1 : tris successifs (du moins prioritaire au plus prioritaire)
par_nom = sorted(eleves, key=lambda e: e["nom"])
par_classe_puis_nom = sorted(par_nom, key=lambda e: e["classe"])

for e in par_classe_puis_nom:
    print(e["classe"], e["nom"])
# 1G2 Alice
# 1G2 Chloé
# 1G2 Dimitri
# 1G3 Bob

par_classe_puis_nom = sorted(
    eleves,
    key=lambda e: (e["classe"], e["nom"]),
)

sort() vs sorted()

nombres = [3, 1, 2]
nombres.sort()
print(nombres)  # [1, 2, 3]

nombres.sort(reverse=True)
print(nombres)  # [3, 2, 1]

Cas particuliers et pièges

• Tri sur une chaîne accentuée : "é" n'est pas placé entre "e" et "f" mais après tous les caractères ASCII. Pour un tri linguistique correct, utiliser le module locale (hors programme).
• Mélanger types et None : sorted([1, None, 2]) lève TypeError. Filtrer ou normaliser avant.
• Sensibilité à la casse : "alice" > "Bob" en ASCII (minuscules > majuscules). Pour un tri insensible : key=lambda e: e["nom"].lower().

Pour aller plus loin

Les algorithmes de tri que vous étudierez en algorithmique ([PH05] : tri par insertion, tri par sélection) sont au cœur de ce que fait sorted() — mais Python utilise en réalité un tri plus sophistiqué (Timsort) dont la complexité est $\mathcal{O}(n \log n)$.