[[{"text":"","title":"Tri d'une table"}],[{"text":"

Lorsque l'on manipule des données en table, il est fréquent de vouloir les trier. 

Prénom
Année
Note 1
Note 2
Appréciation
Stéphane
2000
12.5
9.4
AB
Paul
2003
14
17
B
Régis
2002
9
15
TB
Bernard
2001
5.5
12
B
Franck
1999
16
14.5
AB
Léon
2004
14
16
TB
Table : Une table des élèves

Si on prend l'exemple de la table d'élèves, on peut vouloir par exemple :\n- afficher la liste de tous les élèves par ordre alphabétique;\n- trier les élèves selon une note obtenue à un contrôle.\n- ...

Nous avons écrit des programmes pour trier des tableaux d'entiers, avec le tri par sélection ou le tri par insertion.

Nous pourrions adapter ces programmes pour trier à la place un tableau contenant des dictionnaires.

II suffirait pour cela de remplacer les comparaisons d'entiers par une autre fonction, comparant cette fois deux élèves.

Si par exemple on veut trier les élèves par ordre alphabétique, on peut définir une fonction comme

def compare_prenom(e1 , e2) :\n  return el[prenom\"] < e2[prenom\"]\n

et l'utiliser ensuite à in place de l'opération < dans nos programmes de tri. 

Cependant, cette methode nous oblige à réécrire le programme de tri, ce qui n'est pas idéal, et qui plus est à le réécrire chaque fois que l'ordre change. 

Si demain on veut classer les élèves selon leur note, il faut modifier le programme de tri ou en écrire un autre.\n

Dans ce chapitre, nous allons présenter des fonctions de tri offertes par le langage Python, qui peuvent notamment être utilisées pour trier des données en table.

Dans la suite, nous utiliserons le tableau élèves de dictionnaires contenant les champs Prénom (chaine), Année(entier), Note 1, Note 2 (réel) et appréciation(chaine). Cette table a été obtenu à partir du fichier eleve.csv

"}],[{"text":"Vous utiliserez la table élèves ci-dessous pour la séquence."}],[{"text":"

Dans la séquence précédente, nous avons vu que Python offre des opérations de tri et notamment une fonction sorted.

Celle-ci prend en argument un tableau et en renvoie une version triée, sous la forme d'un nouveau tableau.

tab = [55,2,1,34,3,21,5,8,13,1,0]\nprint(\"tab : \", tab)

tab2 = sorted(tab) \t\t\t\t\t\n

print(\"tab2:\",tab2)
print(\"tab :\", tab)\t\t\t\t\t
Ecrire et tester le code. 
On voit que le tableau de départ n'a pas été modifié
cette fonction a comparé les éléments, qui sont des entiers, avec l'ordre usuel.
Si on lui passe un tableau contenant des éléments d'un autre type, par exemple des chaines de caractères, alors il sera également trié, cette fois par ordre alphabétique.
>>>sorted([\"banane\", \"pomme\", \"cassis\", \"fraise\"]) ['banane', 'cassis', 'fraise', 'pomme']

Ecrire et tester le code ci-dessus.
Mais si en revanche on essaye de trier le tableau eleves avec cette fonction, on obtiendra une erreur.
Faire le teste
>>> sorted (eleves)

Traceback (most recent call last):\nFile \"tri_table.py\", line 16, in <module>\naff iche (sorted (t))\nTypeError: unorderable types: dictO < dict()\n

Ici, le message d'erreur nous explique que Python ne sait pas comparer deux objets qui sont des dictionnaires.

","title":"Trier des données en fonction d'une clé"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"

Pour utiliser la fonction sorted sur notre tableau de dictionnaires, il faut indiquer comment se ramener à des valeurs que Python sait comparer (nombres, chaines de caractères, n-uplets).

Pour cela, on commence par définir une fonction qui prend en argument un élève et renvoie la valeur que l'on souhaite comparer, ici le prénom.\n

def prenom(x) :\n   return x[\"prenom\"]\n

Puis, on peut appeler la fonction sorted sur le tableau eleves en précisant qu'il faut utiliser la fonction prenom(x) à chaque fois que deux éléments doivent \n

eleves = [{'prenom': 'Stéphane', 'annee': 2000, 'note1': 12.5, 'note2': 9.4, 'appreciation': 'AB'}, {'prenom': 'Paul', 'annee': 2003, 'note1': 14.0, 'note2': 17.0, 'appreciation': 'B'}, {'prenom': 'Régis', 'annee': 2002, 'note1': 9.0, 'note2': 15.0, 'appreciation': 'TB'}, {'prenom': 'Bernard', 'annee': 2001, 'note1': 5.5, 'note2': 12.0, 'appreciation': 'B'}, {'prenom': 'Franck', 'annee': 1999, 'note1': 16.0, 'note2': 14.5, 'appreciation': 'AB'}, {'prenom': 'Léon', 'annee': 2004, 'note1': 14.0, 'note2': 16.0, 'appreciation': 'TB'}]

def prenom(x) :
   return x[\"prenom\"]
tab_tri_eleves = sorted(eleves, key=prenom)

print(tab_tri_eleves)
Ecrire et tester le code.
Vérifier que le tableau est bien classé par ordre alphabétique.
Donc, on dispose maintenant d'un nouveau tableau, tab_tri_eleves, dans lequel les éléments sont maintenant triés par ordre alphabétique selon l'attribut prenom.

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

Tester le code précédent avec l'option  reverse=True.

"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"

Supposons que nous venons de trier nos élèves selon la note qu'ils ont obtenue au dernier contrôle, par exemple pour afficher les résultats.
Si beaucoup d'élèves se trouvent avoir la même note, il peut être judicieux de trier aussi par ordre alphab&tique les élèves qui ont la même note.
Ainsi, nous retrouverons plus facilement leur nom dans la liste.
Lorsque l'on trie comme cela selon deux critères, d'abord selon le premier puis, à valeur égale, selon le second, on appelle cela un ordre lexicographique.
Il se trouve que la comparaison (< ou >) de Python à la propriété de réaliser un ordre lexicographique.
>>> (1,3)<(1,7)\nTrue\t\t\t\t\n>>> (1,7)<(1,4)\nFalse\t\t\t\t\n>» (1,\t7)\t<\t(2, \t4)\nTrue\t\t\t\t\n
On peut donc en tirer parti pour trier très facilement nos éléments selon la note, puis selon le nom.
eleves = [{'prenom': 'Stéphane', 'annee': 2000, 'note1': 12.5, 'note2': 9.4, 'appreciation': 'AB'}, {'prenom': 'Paul', 'annee': 2003, 'note1': 14.0, 'note2': 17.0, 'appreciation': 'B'}, {'prenom': 'Régis', 'annee': 2002, 'note1': 9.0, 'note2': 15.0, 'appreciation': 'TB'}, {'prenom': 'Bernard', 'annee': 2001, 'note1': 5.5, 'note2': 12.0, 'appreciation': 'B'}, {'prenom': 'Franck', 'annee': 1999, 'note1': 16.0, 'note2': 14.5, 'appreciation': 'AB'}, {'prenom': 'Léon', 'annee': 2004, 'note1': 14.0, 'note2': 16.0, 'appreciation': 'TB'}]\n\ndef note_puis_nom(x):\n   return x[\"note2\"], x[\"prenom\"]\n\nliste_a_afficher = sorted (eleves, key=note_puis_nom)\n\nprint(liste_a_afficher)\n\n
Ecrire et tester le code.
Ainsi, la fonction sorted va comparer les paires renvoyées par notre fonction note_puis_nom, ce qui aura l'effet escompté.\n

","title":"Ordre lexicographique et stabilite"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"

Il y a une autre manière de parvenir au même résultat.

Supposons que notre liste d'éléves soit déjà triée par ordre alphabetique, ce qui est tout à fait réaliste.

Lorsqu'on le trie ensuite selon la note, il suffit que les élèves ayant la même note restent dans leur position relative. Un tri qui a cette caractéristique s'appelle un tri stable.

Le tri par sélection, en revanche, ne l'est pas.\nIl se trouve que la fonction sorted fournie par Python réalise un tri stable.  On peut donc trier par selon les notes de notre tableau d'élèves déjà trié par ordre alphabétique pour obtenir le résultat désire.\n

De manière plus générale, on peut appliquer successivement plusieurs tris stables à une table, selon des critères différents, et obtenir ainsi un ordre lexicographique. 

Il faut prendre soin, cependant, de faire les tris dans l'ordre inverse de priorité. Dans notre exemple, il faut ainsi trier d'abord par nom, puis par note.

","title":"Stabilité"}],[{"text":"

Python fournit une autre fonction pour trier des données, avec la notation tableau : sort().

A la différence de sorted, on n'obtient pas un nouveau tableau. Au lieu de cela, le tableau est modifié, pour se retrouver trié au final.

On dit qu'il s'agit la d'un tri en place. On économise ainsi de la mémoire.

Les tris par sélection et par insertion décrits à la séquence précédente sont deux exemples de tri en place.

La fonction sort() accepte les mêmes options key et reverse que la fonction sorted.

On peut donc trier nos élèves par ordre alphabétique par rapport au prénom de la manière suivante:

eleves.sort(key=prenom)\n

Ici, Il n'y a pas de résultat à stocker dans une variable comme nous l'avons fait  avec sorted.

Le contenu de eleves a été modifié. 

Comme pour sorted, la fonction sort garantit un tri stable.\n

eleves = [{'prenom': 'Stéphane', 'annee': 2000, 'note1': 12.5, 'note2': 9.4, 'appreciation': 'AB'}, {'prenom': 'Paul', 'annee': 2003, 'note1': 14.0, 'note2': 17.0, 'appreciation': 'B'}, {'prenom': 'Régis', 'annee': 2002, 'note1': 9.0, 'note2': 15.0, 'appreciation': 'TB'}, {'prenom': 'Bernard', 'annee': 2001, 'note1': 5.5, 'note2': 12.0, 'appreciation': 'B'}, {'prenom': 'Franck', 'annee': 1999, 'note1': 16.0, 'note2': 14.5, 'appreciation': 'AB'}, {'prenom': 'Léon', 'annee': 2004, 'note1': 14.0, 'note2': 16.0, 'appreciation': 'TB'}]

def prenom(x) :
   return x[\"prenom\"]
print(\"non trié : \",eleves)
eleves.sort( key=prenom)
print(\"trié : \",eleves)

","title":" Trier en place"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"

L'algorithme des plus proches voisin travaille à partir d'une table de données et nécessite de déterminer les k lignes  \"les plus proches\" du point cherché.

Une manière simple pout isoler les k plus proches voisins consiste à trier l'intégralité de la table par ordre de proximité avec le point cherché, pour ensuite prendre les k premières lignes.\n

Supposons que l'on considère une table de données t dont chaque ligne désigne un point avec des coordonnées (attributs \"x\" et \"y\") et une classe ou une valeur (attribut \"valeur\"), et que l'on essaie d'estimer la classe ou valeur associée à un point A dont les coordonnées sont données par distance_de_A qui prend en paramètre une ligne de la table et renvoie la distance entre le point décrit par cette ligne et A.\n

t=[{'x': 32, 'y': 70}, {'x': 19, 'y': 7}, {'x': 35, 'y': 35}, {'x': 86, 'y': 48}, {'x': 95, 'y': 43}, {'x': 56, 'y': 31}, {'x': 32, 'y': 71}, {'x': 27, 'y': 2}, {'x': 9, 'y': 64}, {'x': 74, 'y': 31}, {'x': 89, 'y': 59}, {'x': 49, 'y': 22}, {'x': 34, 'y': 66}, {'x': 20, 'y': 53}, {'x': 41, 'y': 70}, {'x': 48, 'y': 93}, {'x': 24, 'y': 28}, {'x': 65, 'y': 46}, {'x': 53, 'y': 8}, {'x': 52, 'y': 87}, {'x': 91, 'y': 12}, {'x': 17, 'y': 75}, {'x': 82, 'y': 70}, {'x': 67, 'y': 12}, {'x': 91, 'y': 12}, {'x': 11, 'y': 7}, {'x': 92, 'y': 71}, {'x': 21, 'y': 53}, {'x': 56, 'y': 35}, {'x': 86, 'y': 6}, {'x': 21, 'y': 1}, {'x': 10, 'y': 97}, {'x': 63, 'y': 14}, {'x': 74, 'y': 59}, {'x': 32, 'y': 49}, {'x': 23, 'y': 11}, {'x': 80, 'y': 9}, {'x': 46, 'y': 28}, {'x': 72, 'y': 27}, {'x': 18, 'y': 81}, {'x': 83, 'y': 50}, {'x': 51, 'y': 50}, {'x': 82, 'y': 43}, {'x': 97, 'y': 17}, {'x': 54, 'y': 28}, {'x': 87, 'y': 41}, {'x': 83, 'y': 72}, {'x': 69, 'y': 28}, {'x': 26, 'y': 90}]\n

y = float (input(\"ordonnee de A: \"))\n

def distance_de_A(p) :\n   return math.sqrt((p['x'] - x)**2 +  ((p['y'] - y) ** 2)

Il ne reste plus qu'a utiliser la fonction sorted sur notre table t avec comme cle de tri notre fonction distance_de_A.

tri_t = sorted(t, key=distance_de_A)

print(tri_t)

Ecrire et tester le code.

En déduire le point le plus proche de A(50,50).

On obtient ainsi une table tri_t avec les même lignes que t, mais triées par ordre de proximité au point A.

On a alors toute liberté de sélectionner les k premieres lignes avec :

plus_proches = [ tri_t[i] for i in range(k)]

pour ensuite déterminer la moyenne ou la majorité des valeurs de ces lignes.

Mise en oeuvre plus efficace\nIl y a une certaine inefficacité à trier l'intégralité de la table pour n'en garder que les quelques premiers éléments. notamment si la table est très grande et le nombre des voisins qui nous intéresse est faible. 

Pour une meilleure efficacité on pourra opter pour une variante des algorithmes vus à la séquence précédente dans laquelle on ne conserve jamais plus de k éléments triés.

","title":"Application : Recherche des plus proches voisins"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"

Expliquer comment procéder pour trier le tableau élèves\n• par année;\n• par année et pour la même appréciation.

","title":"Exercice 1"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"

Expliquer pourquoi le tri par insertion de la séquence précédente est effectivement stable.

","title":"Exercice 2"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"

Réaliser des expériences pour tester que la fonction sorted réalise effectivement un tri stable.\t

","title":"Exercice 3"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"

On suppose qu'une table de données dont chaque ligne représente une activité et présente trois champs :\n- le numéro de l'activité (\"num\");\n- son heure de début (\"debut\");\n- son heure de fin (\"fin\").

Ces trois champs contiennent des nombres entiers positifs ou nuls.

Trier la table par ordre d'heure de fin croissante.

","title":"Exercice 4"},{"input":"","place":"Ecrire le résultat ici."}]]