[[{"text":"","title":"Tri d'une table"}],[{"text":"
Lorsque l'on manipule des données en table, il est fréquent de vouloir les trier.
Si on prend l'exemple de la table d'élèves manipulée dans les chapitres précédents, 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 a le reecrire chaque fois que l'ordre change. Si demain on veut classer les eleves selon leur note, il faut modifier le programme de tri ou en ecrire un autre.\nDans ce chapitre, nous allons presenter des fonctions de tri offertes par le langage Python, qui peuvent notamment etre utilisees pour trier des donnees tn.hlp. Dans cp ani suit. on sunnose au'on a chargé le contenu d'un fichier\neleves. csv et construit un tableau eleves de dictionnaires contenant des champs prenom (chaine), jour, mois et armee (entiers) et proj et (chaine).\n17
"}],[{"text":"
Dans la section 10.4, nous avions rapidement evoque le fait que Python offre des operations de tri et notamment une fonction sorted. Celle-ci prend en argument un tableau et en renvoie une version triee, sous la forme d'un nouveau tableau.\n>» t = [21, 13, 34, 8] >>> sorted (0\n[8, 13, 21, 34]\nOn peut verifier que le tableau de depart n'a pas ete modifie.\n>>> t\n[21, 13, 34, 8]\ncette fonction a compare les elements, qui sont des entiers, avec l'ordre usuel. Si on lui passe un tableau contenant des elements d'un autre type, par exemple des chaines de caracteres, alors il sera egalement trie, cette fois pour l'ordre alphabetique.\n>>> sorted([\"banane\", \"pomme\", \"cassis\", \"fraise\"]) ['banane', 'cassis', 'fraise', 'pomme']\nMais si en revanche on essaye de trier le tableau contenant nos eleves avec cette fonction, on obtient une erreur.\n>>> sorted (eleves)\nTraceback (most recent call last):\nFile \"tri_table.py\", line 16, in <module>\naff iche (sorted (t))\nTypeError: unorderable types: dictO < dict()\nIci, le message d'erreur nous explique que Python ne sait pas comparer deux objets qui sont des dictionnaires. Pour utiliser la fonction sorted sur notre tableau de dictionnaires, il faut indiquer comment se ramener A des valeurs que Python sait comparer (nombres, chaines de caracteres, n-uplets). Pour cela, on commence par definir une fonction qui prend en argument un eleve et renvoie la valeur que l'on souhaite comparer, ici le prenom.\ndef prenom(x) :\nreturn x [\"prenom\"]\nPuis, on peut appeler la fonction sorted sur le tableau eleves en precisant qu'il faut utiliser la fonction prenom chaque fois que deux elements doivent\ntri_eleves = sorted(eleves, key=prenom)\n(Cette syntaxe est analogue a end=\" \" pour la fonction print.) On dispose maintenant d'un nouveau tableau, tri_eleves, dans lequel les elements (c'est-a-dire les dictionnaires representant les eleves) sont maintenant tries par ordre alphabetique de prenom.\nSi on veut trier plutot dans l'ordre inverse, c'est-à-dire du plus grand au plus petit, il faut passer une autre option a la fonction sorted, a savoir reverse=True.\ntri_eleves = sorted(eleves, key=prenom, reverse=True)
","title":"Trier des données en fonction d'une clé"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"
Supposons que nous venous de trier nos eleves selon la note qu'ils ont obtenue au dernier controle, par exemple pour afficher les resultats. Si beau-coup d'eleves se trouvent avoir la merne note, il peut etre judicieux de trier aussi par ordre alphabetique les eleves qui ont la meme note. Ainsi, us retrouveront plus facilement leur nom dans la liste. Lorsque l'on trie comme cela selon deux criteres, d'abord selon le premier puis, a valeur egale, selon le second, on appelle cela un ordre lexicographique. Ii se trouve que la comparaison de Python a la propriete de realiser un ordre lexicographique.\n>» (1,\t3)\t<\t(1,\t7)\nTrue\t\t\t\t\n>» (1,\t7)\t<\t(1, \t4)\nFalse\t\t\t\t\n>» (1,\t7)\t<\t(2, \t4)\nTrue\t\t\t\t\nOn peut done en tirer parti pour trier tres facilement nos &eves selon la note puis selon le nom.\ndef note_puis_nom(x):\nreturn x[\"note\"], x[\"nom\"]\nliste_a_afficher = sorted (eleves, key=note_puis_nom)\nAinsi, la fonction sorted va comparer les paires renvoy6es par notre fonction note_puis_nom, ce qui aura l'effet escompte.\nStabilite\nIi y a une autre fawn de parvenir au meme resultat. Supposons que notre liste d'eleves soit déjà triee par ordre alphabetique, ce qui est tout a fait realiste. Lorsqu'on la trie ensuite selon la note, il suffit que les eleves ayant la meme note restent dans leur position relative. Un tri qui a cette\nr\tA+A\t7, V\",\t4-4\tT\t1- •\nZZO\t.L I.\tIII LI sa\necrit plus haut (programme 15 page 148), est stable. Le tri par selection, en revanche, ne l'est pas.\nIi se trouve que la fonction sorted fournie par Python realise un tri stable (ii faut lire la documentation pour le savoir). On peut donc trier selon les notes notre tableau d'eleves déjà trie par ordre alphabetique pour obtenir le resultat desire.\nDe maniere plus generale, on peut appliquer successivement plusieurs tris stables a une table, selon des criteres differents, et obtenir ainsi un ordre lexicographique. Ii faut prendre soin, cependant, de faire les tris dans l'ordre inverse de priorite. Dans notre exemple, il faut ainsi trier d'abord par nom, puis par note.
","title":"Ordre lexicographique et stabilite"},{"input":"","place":"i"}],[{"text":"
Python fournit une autre fonction pour trier des donnees, avec la notation tableau. sort 0. A la difference de sorted, on n'obtient pas un nouveau tableau. Au lieu de cela, le tableau est modifie, pour se retrouver trie au final. On dit qu'il s'agit la d'un tri en place. On economise ainsi de la memoire. Les tris par selection et par insertion decrits au chapitre 10 sont deux exemples de tri en place.
La fonction sort accepte les memes options key et reverse que la fonction sorted. On peut done trier nos eleves par ordre alphabetique de prenom de la maniere suivante.\neleves.sort(key=prenom)\nIci, ii n'y a pas de resultat a stocker dans une variable comme nous le faisions avec sorted. Le contenu de eleves a ete modifie. Conime pour sorted, la fonction sort garantit un tri stable.\n
","title":" Trier en place"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"
L'algorithme des plus proches voisins (chapitre 13) travaille a partir d'une table de donnees et necessite de determiner les k lignes c les plus proches » du point cherche. Une maniere simple, bien que pas la plus efficace, d'isoler les k plus proches voisins consiste a trier Pintegralite de la table par ordre de proximite avec le point cherche, pour ensuite prendre les k premieres lignes.\nSupposons que Pon considere une table de donnees t dont chaque ligne designe un point avec des coordonnees (attributs \"x\" et \"y\") et une classe ou une valeur (attribut \"valeur\"), et que l'on essaie d'estimer la classe ou valeur associee a un point A dont les coordonnees sont donnees par\ndistance_de_A qui prend en parametre une ligne de la table et renvoie la distance entre le point decrit par cette ligne et A.\nx = float(input(\"abscisse de A: \"))\ny = float (input(\"ordonnee de A: \"))\ndef distance_de_A(p) :\nreturn math.sqrt((p['x'] - x) ** 2 + (pPy'l - y) ** 2)\nII ne reste alors plus qu'a utiliser la fonction sorted sur notre table t avec comme cle de tri notre fonction distance_de_A.\ntri_t = sorted(t, key=distance_de_A)\nOn obtient ainsi une table tri_t avec les tames lignes que t, mais triees par ordre de proximite au point A. On a alors toute liberte d'en selectionner les k premieres lignes avec\nplus_proches = [ tri_t [i] for I in range(k) ]\npour ensuite determiner la moyenne ou la majorite des valeurs de ces lignes.\nMise en oeuvre plus efficace. II y a one certaine inefficacite a trier l'integralite de la table pour n'en gatder clue les quelques premiers elements. notamment si la table est tres grab de et le Hombre des voisins qui nous intere.sse pet it. Poor we meilleure efficacite on pourra opter pour one variante des algorithmes vits all chapitre 10 clans laquelle on ne conserve jai:mils plus de k elements tries. Voir exereice 145 page 152.\nA retenir. Pour trier des donnees en table, on peut utiliser les fonctions de tri fournies par Python. ii savoir sorted et sort. La premiere renvoie on nouveau tableau et la second trie en place. Ces deux functions assure la stabilite. c'est-h-dire qu'elles eonservent l'ordre respectif des elements gaux.\n
","title":"Application : recherche des plus proches voisins"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"
Expliquer comment proceder pour trier le tableau eleves\n•\tpar mois de naissance (pour feter les anniversaires);\n•\tpar mois de naissance et, pour un merne mois, par jour de naissance;\n•\tpar age, c'est4-dire par date de naissance.
","title":"Exercice 1"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"
Expliquer pourquoi le tri par insertion du programme 15\npage 148 est effectivement stable.
","title":"Exercice 2"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"
Réaliser des experiences pour tester que la fonction sorted\nrealise effectivement un tri stable.\t
\n
","title":"Exercice 3"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"
Probleme du sac a dos : programmation. On reprend le probleme du sac a dos (exercices 158 et 159 page 171). On suppose que les valeurs et poids des objets sont stock& dans une table de donnees. Ecrire des programmes utilisant chacune des trois strategies gloutonnes de l'exercice 159 pour calculer une valeur qui pent etre emportee.\n
","title":"Exercice 4"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"
On reprend le probleme de selection des activites de l'exercice 164 page 172. On suppose cette fois disposer d'une table de donnees dont chaque ligne represente une activite et presente trois champs : le numero de Factivite (\"num\"), son heure de debut (\"debut\") et son heure de fin (\"fin\"). Ces trois champs contiennent des nombres entiers positifs ou nuls.\nOn souhaite ecrire une fonction de selection d'activites suivant la meme strategie gloutonne, mais plus efficace que celle developpee a l'exercice 165. Pour cela on propose de prealablement trier le tableau par ordre d'heure de\nfin croissante. Indication : une boucle suffit.
","title":"Exercice 5"},{"input":"","place":"Ecrire le résultat ici."}]]
