Tri d'une table

Lorsque des données sont regroupées dans une table, il peut être intéressant de pouvoir le trier. Par exemple, on peut vouloir afficher la liste de tous les élèves par ordre alphabétique ou bien encore trier les élèves selon leur date de naissance, selon la note obtenue à un contrôle...

Reprenons notre exemple avec les élèves de la classe :

prénom	jour	mois	année	sexe	projet
Louan	13	4	2003	G	être heureux
Mael	29	3	2003	G	manger une glace
Alexis	20	10	2003	G	gagner au loto
Théo	25	4	2003	G	avoir une bonne note au prochain devoir
Arthur	14	1	2003	G	devenir quelqu’un de célèbre
Tristan	18	9	2003	G	gagner le Tour de France
...	...	...	...	...	...

On rappelle que les données de ce fichier CSV peuvent être mémorisées dans un tableau de dictionnaires appelé eleves comme suit :

import csv
fichier = open('eleves.csv', 'r', encoding = 'UTF-8')
t = csv.DictReader(fichier, delimiter=',')
eleves = [dict(ligne) for ligne in t] # création et construction du tableau par compréhension
print(eleves) # pour afficher le contenu du tableau 'eleves'

Les algorithmes de tri par sélection ou de tri par insertion que nous avons écrits permettent de trier des tableaux d'entiers. On pourrait l'adapter pour trier un tableau de dictionnaires : il suffirait de remplacer l'opérateur de comparaison des entiers (< ou >) par une autre fonction, comparant deux élèves.

Par exemple, si on souhaite trier les élèves par ordre alphabétique, on peut définir une fonction de comparaison comme

def compare_prenom(e1, e2):
    """compare les prénoms des élèves e1 et e2
    e1 et e2 sont deux dictionnaires"""
    return e1["prénom"] < e2["prénom"]

compare_prenom(eleves[0],eleves[1]) # Louan et Mael ne sont pas ordonnés par ordre alphabétique

compare_prenom(eleves[0], eleves[2]) # Louan et Alexis ne sont pas ordonnés par ordre alphabétique

def tri_par_insertion(T):
    for i in range(1,len(T)):
        x = T[i]
        j = i
        while j>0 and compare_prenom(x, T[j-1]):  # modification nécessaire
            T[j] = T[j-1]
            j = j - 1
        T[j] = x

tri_par_insertion(eleves)
eleves

Cette façon de faire possède le gros désavantage de devoir modifier l'algorithme de tri, et de le réécrire à chaque fois que l'on veut trier selon un autre ordre (critère).

C'est pour cela, que nous allons uniquement utiliser les fonctions de tri offertes par Python.

Fonctions de tri offertes par Python

Python offre deux fonctions permettant d'effectuer des opérations de tri.

La fonction sorted

Celle-ci prend en argument un tableau et renvoie un nouveau tableau, trié, contenant les mêmes éléments.

t = [12, 5, 3, 6, 8, 10]
sorted(t)

t

On voit que t n'a pas été modifié.

Cette fonction permet aussi de trier des chaînes de caractères, en utilisant l'odre alphabétique.

sorted(["poire", "pomme", "cerise", 'kiwi'])

La fonction sort

Celle-ci s'applique à un tableau, ne renvoie rien, mais modifie le tableau d'origine.

t.sort()
t

On voit que t a été modifié.

On peut aussi trier directement un tableau de chaînes de caractères avec sort.

fruits = ["poire", "pomme", "cerise", 'kiwi']
fruits.sort()
fruits

Ordre lexicographique

Il est possible de trier des données selon plusieurs critères. Ainsi, lorsque l'on trie selon un premier critère puis, à valeurs égales, selon un second critère, on appelle cela un ordre lexicographique.

(2, 3) < (2, 8)

(2, 3) < (2, 1)

(1, 5) < (2, 3)

Les fonctions sorted et sort utilisent cet ordre lexicographique pour trier un tableau.

sorted([(2, 3), (1, 5), (2, 8), (2, 1)])

Exercice 1 : Que renvoie l'expression suivante ?

sorted([(1, 3), (1, 2), (2, 4), (2, 1)])

Réponse :

Exercice 2 : Que renvoie l'expression suivante ?

sorted([(1, "poires"), (3, "abricot"), (1, "bananes"), (2, "kiwi")])

Réponse :

Trier des données en fonction d'une clé

Revenons à notre tableau d'élèves.

import csv
fichier = open('eleves.csv', 'r', encoding = 'UTF-8')
t = csv.DictReader(fichier, delimiter=',')
eleves = [dict(ligne) for ligne in t] # création et construction du tableau par compréhension
print(eleves) # pour afficher le contenu du tableau 'eleves'

Les deux fonctions sorted et sort sont incapables de comparer deux dictionnaires. En particulier, on ne peut pas appliquer directement ces fonctions à notre tableau eleves.

sorted(eleves)

Trier selon un critère unique

Pour pouvoir utiliser ces fonctions, il va falloir leur donner en paramètre ce que l'on appelle une clé. Cette clé est en fait une fonction qui prend en paramètre un éleve et qui renvoie la valeur que l'on souhaite comparer. Cela doit nécessairement être des éléments que Python sait comparer (nombres, chaînes de caractères, tuples).

Si on veut comparer les prénoms des élèves (pour faire un tri par ordre alphabétique des prénoms), on peut définir la fonction suivante.

def prenom(x):
    return x["prénom"]

Ensuite, on peut appeler la fonction sorted sur le tableau eleves en précisant qu'il faut utiliser la fonction prenom à chaque fois que deux éléments du tableau doivent être comparés. On l'indique en passant key=prenom à la fonction sorted.

tri_eleves = sorted(eleves, key=prenom)
tri_eleves

Si on veut trier plutôt dans l'ordre inverse, c'est-à-dire du plus grand au plus petit, il faut passer une autre option à la fonction sorted, à savoir reverse=True.

tri_eleves = sorted(eleves, key=prenom, reverse=True)
tri_eleves

Exercice 3 : Triez la table eleves suivant l'année de naissance des élèves. Indication : n'oubliez pas de commencer par définir la fonction qui servira de clé de tri à la fonction sorted.

Trier selon plusieurs critères

Imaginons que l'on souhaite trier les élèves selon leur année de naissance, puis, si deux élèves sont nés la même année, les trier par ordre alphabétique.

On peut alors utiliser le fait que la fonction sorted réalise l'ordre lexicographique. Il suffit de définir la fonction de tri suivante.

def annee_puis_prenom(x):
    return int(x["année"]), x["prénom"] # ne pas oublier de convertir l'année en entier

Cette fonction renvoie pour chaque élève x, la paire (année, prénom). En utilisant cette, clé, la fonction sorted va utiliser cette fonction pour comparer deux élèves, en respectant l'ordre lexicographique (d'abord l'année, puis en cas d'égalité le prénom).

table_a_afficher = sorted(eleves, key=annee_puis_prenom)
table_a_afficher

Exercice 4 : Triez les élèves de la table eleves par date de naissance (année/mois/jour) du plus vieux au plus jeune.

Application : les prénoms à Angers en 2019

Pour illustrer les fonctions de tris, nous allons maintenant travailler sur des données réelles et plus nombreuses : les prénoms donnés à Angers en 2019. Il est possible de récupérer ce genre de données sur le site d'Open Data de la ville d'Angers ou directement ici.

Le fichier CSV appelé prenoms2019.csv contenant ces données est à télécharger sur info-mounier.fr et à placer dans le même répertoire que ce Notebook. Voici le contenu du début de ce fichier :

COLL_NOM	COLL_INSEE	ENFANT_SEXE	ENFANT_PRENOM	NOMBRE_OCCURRENCES	ANNEE
ANGERS	49007	F	Louise	42	2019
ANGERS	49007	F	Ambre	30	2019
...	...	...	...	...	...

La documentation de ce jeu de données indique que seuls les prénoms donnés au moins 4 fois apparaissent.

Attention : comme beaucoup de données françaises, le caractère de séparation est le point-virgule (;) et non la virgule. Il faudra juste l'indiquer pour importer correctement les données dans le tableau prenoms2019 comme ci-dessus.

import csv
fichier2019 = open('prenoms2019.csv', 'r', encoding = 'utf8')
t = csv.DictReader(fichier2019, delimiter=';') # ATTENTION : le point-virgule est le caractère de séparation
prenoms2019 = [dict(ligne) for ligne in t]
prenoms2019

Exercice 5

1. Triez les prénoms de la table prenoms2019 par ordre alphabétique.

1. Triez les prénoms de la table prenoms2019 du plus fréquent au moins fréquent.

1. Triez par ordre alphabétique puis triez le tableau obtenu par nombre d'occurrences décroissant. Que permet ces 2 tris successifs ?

1. Construisez une nouvelle table contenant uniquement les prénoms et nombres d'occurrences correspondant au tri précédent. (Révisions Séquence 3, Chapitre 4)

Fusion d'une table

Souvent on dispose de plusieurs tables et il est intéressant de pouvoir combiner les jeux de données en une seule table : on parle alors de fusion de tables.

Nous allons voir deux façons de faire :

• la réunion de tables qui permet de réunir deux tables mais n'a de sens que si celles-ci possèdent les mêmes attributs;
• la jointure de tables qui permet de joindre deux tables n'ayant pas les mêmes attributs mais au moins un attribut en commun.

Réunion de tables

Imaginons que nous récupérions également le jeu de données sur les prénoms donnés à Angers en 2018. Il peut être intéressant de réunir ces données avec celles de l'année 2019 pour former une seule grande table. On pourrait ensuite filtrer, trier ou faire des statistiques sur cette grande table (évolution des prénoms entre 2018 et 2019 par exemple).

Le fichier prenoms2018.csv contenant les prénoms donnés à Angers en 2018 est à télécharger sur info-mounier.fr et à placer dans le même répertoire que ce Notebook. Voici le contenu du début de ce fichier :

COLL_NOM	COLL_INSEE	ENFANT_SEXE	ENFANT_PRENOM	NOMBRE_OCCURRENCES	ANNEE
ANGERS	49007	F	Camille	26	2018
...	...	...	...	...	...

On constate que les attributs sont identiques avec le fichier prenoms2019.csv donc on va pouvoir réunir ces deux tables.

On commence par mémoriser ces deux fichiers dans les tables prenoms2018 et prenom2019 :

import csv
f2018 = open('prenoms2018.csv', 'r', encoding = 'utf8')
t2018 = csv.DictReader(f2018, delimiter=';')
prenoms2018 = [dict(ligne) for ligne in t2018]
f2019 = open('prenoms2019.csv', 'r', encoding = 'utf8')
t2019 = csv.DictReader(f2019, delimiter=';')
prenoms2019 = [dict(ligne) for ligne in t2019]

Pour réunir ces deux tables il suffit d'utiliser l'opérateur + qui concatène les deux tableaux.

prenoms1819 = prenoms2018 + prenoms2019
prenoms1819

Le tableau prenoms1819 obtenu est un nouveau tableau contenant les éléments de prenoms2018 suivis des éléments de prenoms2019.

Exercice 6 : Créez une nouvelle table filles1819 permettant de connaître les prénoms de toutes les filles nées à Angers en 2018 et 2019.

Jointure de tables

Revenons à nos élèves.

prénom	jour	mois	année	sexe	projet
Louan	13	4	2003	G	être heureux
Mael	29	3	2003	G	manger une glace
Alexis	20	10	2003	G	gagner au loto
Théo	25	4	2003	G	avoir une bonne note au prochain devoir
Arthur	14	1	2003	G	devenir quelqu’un de célèbre
Tristan	18	9	2003	G	gagner le Tour de France
Leo	10	5	2003	G	dormir plus longtemps le matin
Valentin	30	12	2003	G	créer un jeu vidéo
Elie	19	2	2003	G	devenir astronaute
...	...	...	...	...	...

Il se trouve que parmi ces élèves, certains ont indiqué l'état de réussite de leur projet :

prénom	état_projet
Alexis	non atteint
Mael	atteint
Haude	non atteint
Leo	non atteint
Théo	atteint

Le fichier resultats.csv contenant ces données est à télécharger info-mounier.fr et à placer dans le même répertoire que ce Notebook.

On mémorise de suite le fichier resultats.csv dans une table appelée resultats.

import csv
f = open('resultats.csv', 'r', encoding = 'utf8')
t = csv.DictReader(f, delimiter=',')
resultats = [dict(ligne) for ligne in t]
resultats

On aimerait créer un nouveau tableau, donnant pour chaque élève qui a indiqué son état de réussite, son prénom, le nom du projet et l'état de réussite du projet. On aimerait donc créer ce tableau :

prénom	projet	état_projet
Mael	manger une glace	atteint
Alexis	gagner au loto	non atteint
Théo	avoir une bonne note au prochain devoir	atteint
Leo	dormir plus longtemps le matin	non atteint
Haude	apprendre à piloter une Formule 1	non atteint

Commençons par définir la fonction qui crée, à partir d'une ligne de la table eleves et d'une ligne de la table resultats, un nouveau dictionnaire représentant la ligne souhaitée.

def fusion(e, r):
    """ e est un dictionnaire de la table eleves ; r est un dictionnaire de la table resultats """
    return {'prénom': e['prénom'], 'projet': e['projet'], 'état_projet': r['état_projet']}

Ce dictionnaire récupère les informations souhaitées dans la table eleves sauf celle sur l'état du projet qui est récupérée dans la table resultats.

L'algorithme de "fusion de table" que l'on souhaite appliquer est une double boucle.

t = []
for e in eleves:
    for r in resultats:
        if e["prénom"] == r["prénom"]:
            t.append(fusion(e,r))
t

De façon plus élégante on peut utiliser une construction en utilisant une double compréhension :

t = [fusion(e,r) for e in eleves for r in resultats if e["prénom"] == r["prénom"]]
t

La double compréhension

for e in eleves for r in resultats

produit toutes les paires (e,r) de lignes de la table eleves et de la table resultats et on ne conserve que celles pour lesquelles les valeurs de l'attribut prénom sont égales dans les deux lignes ! On dit que l'on a fait une jointure de deux tables.

Remarque : La jointure fonctionne correctement car dans notre cas il n'y a pas deux élèves ayant le même prénom. Ainsi, chaque ligne des deux tables de départ possède un identifiant unique qui est le prénom de l'élève. Si par exemple, il y avait deux Théo dans la classe, le test

e["prénom"] == r["prénom"]

aurait été vrai deux fois et on aurait attribué l'état "atteint" aux deux Théo, ce qui n'est pas satisfaisant. On contourne généralement ce problème en attribuant un entier unique pour chaque entrée de la table (0 pour Mael, 1 pour Louan, 2 pour Alexis, etc.). Un élève ne serait alors plus identifié par son prénom mais par ce numéro unique.

Exercice 7 On souhaite joindre les tables prenoms2018 et prenoms2019 afin d'obtenir une nouvelle table evolution contenant les trois attributs suivants : le prénom, le nombre d'occurrences en 2018 et le nombre d'occurrence en 2019.

1. Créez la fonction fusion(prenoms2018, prenoms2019) qui permet de créer les dictionnaires de la nouvelle table souhaitée.

1. Créez une table evolution qui est le résultat de la jointure souhaitée.

1. Triez par ordre alphabétique ce tableau evolution.

Sources :

• Documents ressources du DIU EIL, Université de Nantes
• Numérique et Sciences Informatiques, 1re, T. BALABONSKI, S. CONCHON, J.-C. FILLIATRE, K. NGUYEN, éditions ELLIPSES : Site du livre
• Ressource Eduscol : Manipulation de tables

---

Germain BECKER & Sébastien POINT, Lycée Mounier, ANGERS