[[{"text":"","title":"Algorithmes de tri"}],[{"text":"

Supposons que l'on cherche a déterminer si deux tableaux d'entiers contiennent exactement les mêmes éléments, avec pour chacun le même nombre d'occurrences.

Bien entendu, on va commencer par vérifier que les tableaux ont la même taille. 

On peut ensuite chercher à déterminer si chaque valeur du premier tableau apparait dans le second, et inversement.

Malheureusement, ce n'est pas correct, car cela ne tient pas compte du nombre d'occurrences.

Ainsi, les deux tableaux

   [1,1,2] et [2,1,2]

contiennent les mêmes éléments, mais pas avec les mêmes nombres d'occurrences.

On pourra écrire un programme plus subtil, qui compte, pour chaque valeur du premier tableau, son nombre d'occurrences dans chacun des deux tableaux et les compare.

Ce serait la une solution correcte.\n

Si en revanche les deux tableaux se trouvent triés par ordre croissant.

La comparaison devient beaucoup plus simple. II suffit de vérifier que les valeurs contenues aux mêmes indices sont les mêmes.

Le programme réalise une telle comparaison, en s'arrêtant des que la comparaison échoue. 

def compare_tableaux(t, u):\n    \"\"\"compare deux tableaux de même longueur, supposes tries\"\"\"\n    for i in range(len(t)):\n        if t[i] != u[i] :\n            return False\n    return True\n\ntab1 = [1,3,4,8]\ntab2 = [1,3,5,8]\ntab3 = [1,3,4,8]\n\nprint(\"tab1=tab2 ?\",compare_tableaux(tab1, tab2))\nprint(\"tab1=tab3 ?\",compare_tableaux(tab1, tab3))\n

Ecrire et tester le code.
II est donc facile de comparer le contenu de deux tableaux si ils sont trier. 
Nous allons donc voir  deux algorithmes différents pour le faire.

","title":"Problème : comparer deux tableaux"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"

Autres avantages du tri :
Le tri possède d'innombrables applications. une fois que des données sont triées, on peut déterminer rapidement :\n- sa médiane;\n- si une valeur est présente ou non;\n- etc.

"}],[{"text":"

Le tri par sélection parcourt le tableau de la gauche vers la droite, en maintenant sur la gauche une partie déjà triée et à sa place définitive :

   tab=[1,2,3,4,6,5,8,7]\n     déjà trié | pas encore trié

A chaque étape, on cherche le plus petit élément dans la partie droite non triée, puis on l'échange avec l'élément le plus a gauche de la partie non triée.

Ainsi, la premiere étape va déterminer le plus petit élément et le placer tout à gauche du tableau.

Puis la deuxième étape va déterminer le deuxième plus petit élément et le placer en deuxième position à gauche du tableau.

Par construction, la partie gauche déjà triée ne contient que des éléments inférieurs ou égaux è ceux de la partie droite restante à trier.

Pour réaliser le programme de tri par sélection, il nous faudra 2 fonctions :

- une echange pour échanger les deux éléments d'un tableau t situés aux indices i et j.

- une tri_par_selection qui appellera la fonction echange.

","title":"Tri par sélection"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"

def echange(t , i , j):\n    tmp = t[i]\n    t[i] = t[j]\n    t[j] = tmp\n    return t

tab1 = [3,6,4,1,2,5,3]\n\nprint(\"tab1 : \",tab1)\nprint(\"tab1 : \",echange(tab1,0,3))\n\n

Ecrire et exécuter le code. 

Comme on le voit, la fonction échange se sert d'une variable temporaire tmp pour stocker la valeur t[1], remplace alors t[i] par t[j] , puis enfin remplace t[j] par l'ancienne valeur de t[1] contenue dans tmp.

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

Pour réaliser le tri par sélection proprement dit, on va utiliser une boucle parcourant toutes les cases du tableau, de la gauche vers la droite.

for i in range(len (t)) :\n

Ensuite nous utilisons une 2ème boucle for pour parcourir la partie non trié du tableau.

for j in range(i + 1, len(t)):

Le programme de tri_par_selection devient:

def echange(t , i , j):\n    tmp = t[i]\n    t[i] = t[j]\n    t[j] = tmp\n    return t\n    \ndef tri_par_selection(t):\n    \"\"\"trie le tableau t dams l'ordre croissant\"\"\"\n    for i in range(len(t)):\n        # t[0..i[ est trie et <= a t[i..n]\n        # on cherche le minimum de t[i..n]\n        m = i\n        for j in range(i + 1, len(t)):\n            if t[j] < t[m]:\n                m = j\n        echange(t, i, m)\n    return t\n\ntab1 = [3,6,4,1,2,5,3]\n\nprint(\"tab1 : \",tab1)\nprint(\"tab1 trié : \",tri_par_selection(tab1))\n

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

Il est légitime de se demander si c'est la une manière efficace de trier un tableau.

On peut se poser par exemple la question en ces termes : quel temps faut-il a notre tri par sélection pour trier un tableau de mille éléments, d'un million d'éléments, ou plus encore ?\nRéalisons donc cette expérience : pour plusieurs tailles différentes, construisons un tableau contenant des valeurs aléatoires puis mesurons le temps d'exécution de notre tri par sélection.

taille tableau
temps (s)
1000
0,06
2000
0,13
4000
0,44
8000
1,78
16000
6,79

On obtient le graphique suivant :

Comme on le voit, le temps de calcul augmente rapidement avec la taille du tableau. 

On en est déjà à presque 7 secondes pour trier 16 000 éléments. 

On en déduit qu'il y a peu d'espoir de pouvoir trier des tableaux contenant des millions d'éléments avec l'algorithme de tri par sélection.

 Si on regarde les temps de calcul plus attentivement, on observe également que le temps de calcul n'augmente pas proportionnellement.

On peut expliquer l'allure de la courbe de la manière suivante : 

Dans sa première étape, le tri par sélection parcourt tout le tableau a la recherche de la plus petite valeur, ce qui prend un temps proportionnel a la taille du tableau. 

Appelons n cette taille.

Dans la deuxième étape, on parcourt n — 1 cases du tableau et la recherche du plus petit élément, puis n — 2 cases dans l'étape suivante, et ainsi de suite jusqu'a la dernière étape qui est immédiate car il n'y a plus qu'une seule valeur à examiner.

Au total, on a donc fait :

n+(n-1)+(n-2)+ •••+2+1\n

calculs élémentaires. 

Or cette somme vaut :

    n(n+1)/2

, ce qui croit beaucoup plus vite que n et qui explique les temps de calcul observés dans le tableau ci-dessus.

Nous allons essayer d'améliorer les choses avec un second algorithme de tri.

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

L'algorithme de tri par insertion est souvent utilisé par les joueurs de cartes.
Il suit le même principe que le tri par sélection, en parcourant le tableau de la gauche vers la droite et en maintenant une partie déjà triée sur la gauche :
   tab=[1,2,3,4,6,5,8,7]\n     déjà trié | pas encore trié
Mais plutôt que de chercher la plus petite valeur dans la partie non encore triée, le tri par insertion va insérer la première valeur non encore triée, c'est-à-dire la valeur la plus à gauche dans la partie droite non triée, dans la partie gauche déjà triee.

Pour cela, on va décaler d'une case vers la droite tous les éléments déjà triés qui sont plus grands que la valeur à insérer, puis déposer cette dernière dans la case ainsi libérée


Commençons par écrire une fonction insere(t,i,v) qui réalise l'insertion d'une valeur v dans la partie du tableau t[0],t[1]...t[i], en supposant
que les valeurs t[0],...,t[i-1] sont triées, ce que l'on peut illustrer ainsi:
  
         0             i\n    tab=[élément triés,?,.......]
On va décaler un par un les éléments vers la droite jusqu'à trouver la bonne position j de la valeur v, pour se retrouver au final avec la situation suivante :
         0        j\n    tab=[él.triés,v,él.triés,.......]
Dans un cas extrème, la valeur v est plus grande que toutes les autres et on aura j = i. 
Dans l'autre cas extreme, elle est au contraire plus petite que toutes les autres et on aura j = 0.

","title":"Tri par insertion"},{"input":"","place":"i"}],[{"text":"

 La fonction insere s'écrit avec une boucle while, dont le code est le suivant:
def insere(t , i, v) :\n    \"\"\"insere v dans t[O. i[ suppose trié\"\"\"\n    j = i\n    while j > 0 and t[j - 1] > v:\n        t[j] = t[j - 1]\n        j = j - 1\n    t[j] = v\n    return t\n\n
tab1 = [1,3,4,2,6,5]\n
print(\"tab1 : \",tab1)\nprint(\"tab1 insere : \",insere(tab1,3,tab1[3]))\n

Ecrire et exécuter le code.

Ce code évite soigneusement de déborder à gauche du tableau lorsque la valeur v se trouve être plus petite que toutes les valeurs, grâce au test j > 0 and t[j - 1] > v.

Ainsi, lorsque j atteint la valeur 0, le test j > 0 échoue et le programme ne tente pas d'accéder à t[j - 1], ce qui provoquerait une erreur.

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

Pour écrire la fonction tri_par_insertion, il suffit maintenant d'insérer successivement toutes les valeurs du tableau avec la fonction insere, en procédant de la gauche vers la droite. On le fait avec une simple boucle for. Le code final est le suivant :

def insere(t , i, v) :\n    \"\"\"insere v dans t[O. i[ suppose trié\"\"\"\n    j = i\n    while j > 0 and t[j - 1] > v:\n        t[j] = t[j - 1]\n        j = j - 1\n    t[j] = v\n    return t\n\ndef tri_par_insertion(t):\n    \"\"\"trie /e tableau t dans l'ordre croissant\"\"\"\n    for i in range(1, len(t)):\n        # invariant : t[O. i[  est trié\n        t = insere(t , i , t[i])\n    return t\n\ntab1 = [3,6,4,1,2,5,3]\n\nprint(\"tab1 : \",tab1)\nprint(\"tab1 trié : \",tri_par_insertion(tab1))\n\n
Ecrire et exécuter le code.

Ii est important de faire remarquer qu'un appel a insere (t , i, v) supprime du tableau t la valeur t [i] et y insere la valeur v, possiblement avec un décalage de plusieurs autres valeurs.
 Dans le cas du tri par insertion, on appelle toujours insere avec pour v la valeur de t[i], ce qui garantit bien une permutation des éléments du tableau.\n

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

Dans le pire des cas, le tri par insertion n'est pas meilleur que le tri par selection.

Il faut alors :

 1+2+•••+(n—2)+(n—1) opérations pour trier un tableau de taille n.

En revanche, il existe des situations où le tri par insertion est meilleur que le tri par sélection.

Supposons par exemple que le tableau soit déjà trié et examinons ce qui se passe.

A chaque appel de la fonction insere, la valeur v se trouve être supérieure ou égale à la première valeur du à laquelle elle est compar&e (a savoir t[i - 1] ) et on sort donc immédiatement de la boucle while, sans modification du tableau.

Cet appel à insere s'effectue donc en temps constant. Par conséquent, le tri par insertion se limite à n appels à la fonction insere qui prennent tous un temps constant, d'on un temps total proportionnel à n.

Plus généralement, le tri par insertion se comporte favorablement si le tableau est \"presque trié\", ce qui arrive plus souvent qu'on ne le pense avec des données réalistes.

","title":"Efficacité"},{"htm":"","css":"","js":""}],[{"text":"

Dans nos deux programmes de tri par sélection et par insertion, on a supposé que Ion triait des tableaux d'entiers et on a utilisé la comparaison des entiers fournie par Python (à savoir les opérations < et >).

Mais nous pourrions trier des valeurs qui ne sont pas des entiers, par exemple des chaines de caractères, on encore trier des entiers autrement que par ordre croissant. 

Il faut juste remplacer les opérations < et > de Python dans nos programmes par un appel à une fonction indignant si deux éléments soot bien ordonnés ou non.\nIOU\tLlIdIJILIC\trugurmiules ue LII\nA quelle vitesse peut-on esperer trier? Pour trier un tableau contenant N valeurs, nulls a.VOTIS vu que n.os deux algorithmes de tri, par selection et par insertion, peuvent prendre LIA temps proportionnel a N2 dans le pire des ms. Peut-on esperer faire mieux et quelle est; la limite que l'on peut esperer obtenir '? Si on suppose qu'on ne commit rien quant aux valeurs a trier, notamment leur distribution, et qu'on peut seulement les compare!: deux a deux, alors In theorie nous indique qu'il la.ut au moms N log, N compa,raisons, dans le pine des cas, pour trier N valeurs. La fonction mathernatique log2. appclec logarithme, croft relativement lentement (confine le nombre de chiffres necessaires pour &Tire son argument ). Par exemple, log.,( 109) < 30. II existe plusieurs &gorithmes qui realisent cette borne inferieure (le tri par tas et le tri fusion, par exemple, pour n'en citer que\nSi en revanche on possede uric information (plant a la nature ou la distribution des valeurs, on peut faire encore mieux. Si par exemple on prissede l'infbrination qu'il n'y a que sept valeurs differentes, ou encore qu'il s'agit. &enders compris entre -231 et 231 - 1 (cf chapitre 19), alurs on petit trier N x,aleurs en un temps proportionnel a N. Le t.ri par denombrement en est un exemple (cf exercice 149).\n

","title":"Trier pour un ordre arbitraire"}],[{"text":"

Python fournit des fonctions pour trier des tableaux, plus éfficaces que les tris par sélection et par insertion.
Elles se présentent de deux manières, selon que l'on veut obtenir une copie triée du tableau, sans le modifier, ou au contraire modifier le tableau pour le trier, comme nous l'avons fait.\n
La fonction sorted correspond au premier cas. Elle prend en argument un tableau et renvoie un nouveau tableau, trié, contenant les mêmes éléments.

tab = [55,2,1,34,3,21,5,8,13,1,0]
print(\"tab : \", tab)
tab2 = sorted(tab) \t\t\t\t\t
print(\"tab2:\",tab2)
print(\"tab :\", tab)\t\t\t\t\t
Ecrire et tester le code.
Comme on le voit, le tableau t n'a pas été modifié.
La construction t/sort(), en revanche, modifie le tableau t pour le trier, sans rien renvoyer.
tab = [55,2,1,34,3,21,5,8,13,1,0]
print(\"tab : \", tab)
tab.sort() \t\t\t\t\t
print(\"tab : \",tab)
Ecrire et tester le code.
Ces deux fonctions sont largement plus efficaces que les tris par sélection et par insertion. 

Trier un tableau d'un million d'éléments, par exemple, est instantané.


A retenir. Le tri par selection et, le tri par insertion sont deux algorithrnes de tri elementaires, qui peuvent are utilises pour trier des tableaux. Le tri par insertion a on meilleur comportement rine le tri par selection lorsque le tableau est presque trie. Les deux restent peu efficaces des clue les tableaux contiennent plusieurs milliers d'elements. 11 existe de meilleurs algorithmes de tri, plus complexes, dont eeltti offert par Python avec les fonctions sort et sorted.\n

","title":" Les tris fournis par Python"},{"input":"","place":"Ecrire le résultat ici."}],[{"text":"

En supposant que le tri par sélection prend un temps directement proportionnel à N^2 et qu'il prend 6,8 secondes pour trier 16 000 valeurs. Calculer le temps qu'il faudrait pour trier un million\nde valeurs avec ce merne tri par sélection.

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

Détailler les différentes étapes du programme tri par sélection sur le tableau [3,4,1,7,2]

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

Dans la toute derniere étape du tri par sélection, ii n'y a qu'une seule valeur dans la partie droite et il est done inutile d'y chercher la plus petite valeur ni de rechanger avec elle-même. Modifier le programme tri_par_selection pour éviter cette étape inutile.

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

Détailler les différentes étapes du programme tri_par_insertion sur le tableau [3,4,1,7,2]

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

Que se passe-t-il lorsque le tri par insertion est appliqué à un\ntableau qui se présente en ordre décroissant ?

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

Ecrire une fonction est_trié(t) qui renvoie True si le tableau t est trié par ordre croissant et False sinon.

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

Ecrire une fonction plus_petits qui prend en paramètres un tableau t et un entier k suppose inférieur a la longueur de t et qui renvoie un tableau contenant, dans l'ordre, les k plus petits éléments de t. 

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

Ecrire une fonction \"histo\" qui prend en argument un tableau d'entiers trié et affiche son contenu sous la forme d'un histogramme, c'est-a-dire quelque chose comme :

tab = [0,2,2,3,6,6,6]

histo(tab)

>>>1 fois 0\n   2 fois 2\n   1 fois 3\n   3 fois 6

...

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

En se servant du tri par insertion, écrire une fonction qui prend en argument un tableau d'entiers et renvoie la valeur la plus fréquente dans ce tableau.

Indication : une fois le tableau trié, les valeurs égales se retrouvent cote à cote dans le tableau et il devient facile de les compter.

Une simple boucle et quelques variables suffisent.

\n

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

Si on sait que les valeurs d'un tableau sont des entiers qui ne sont pas trop grands, on peut trier le tableau simplement en comptant le nombre d'occurrences de chaque valeur, puis en réécrivant ensuite dans le tableau autant d'occurrences de chaque valeur, par ordre croissant. 

On appelle cela le tri par dénombrement. 

Pour simplifier un peu les choses, supposons que les éléments à trier sont positifs on nuls et plus petits qu'une constante maxi donnée (par exemple 100). Ecrire une fonction\ntri_par_denombrement qui réalise cet algorithme.

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

 Ecrire une fonction tri_deux_valeurs qui trie un tableau (reçu en argument) qui ne contient que deux valeurs différentes.

On pourra supposer qu'il s'agit des entiers 0 et 1 pour simplifier.

","title":"Exercice 11"}]]

Détails

Écrit par : Richard GAUTHIER

Création : 26 Novembre 2019

Mis à jour : 26 Novembre 2019

Clics : 1836

[[{"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."}]]

Détails

Écrit par : Richard GAUTHIER

Création : 25 Novembre 2019

Mis à jour : 25 Novembre 2019

Clics : 1318

[[{"login":"devoir"}],[{"quiz":830}]]

Détails

Écrit par : Richard GAUTHIER

Création : 24 Novembre 2019

Mis à jour : 4 Décembre 2020

Clics : 1639

[[{"visi":false,"text":"Afin de vérifier vos acquis, répondez aux questions suivantes."}],[{"chrono":45},{"text":"En quelle année est né officiellement la première photographie?"},{"radio":[{"label":"1839","sol":true},{"label":"1739","sol":false},{"label":"1939","sol":false},{"label":"1959","sol":false}]}],[{"chrono":45},{"text":""},{"radio":[{"label":"iodure d'argent","sol":true},{"label":"du cuivre","sol":false},{"label":"du goudron","sol":false},{"label":"du charbon","sol":false}]}],[{"chrono":45},{"text":"A quelles couleurs l'oeil humain est-il plus sensible?"},{"chekbox":[{"label":"Rouge","sol":true},{"label":"Verte","sol":true},{"label":"Bleue","sol":true},{"label":"Jaune","sol":false},{"label":"blanche","sol":false},{"label":"noire","sol":false}]}],[{"chrono":45},{"text":""},{"radio":[{"label":"rgb(0,0,0)","sol":true},{"label":"rgb(255,255,255)"},{"label":"rgb(255,0,0)","sol":false},{"label":"rgb(130,130,130)","sol":false}]}],[{"chrono":45},{"text":"En quelle année a été créé la première photographie couleur?"},{"radio":[{"label":"1861","sol":true},{"label":"1789","sol":false},{"label":"1939","sol":false},{"label":"1959","sol":false}]}],[{"chrono":45},{"text":"En quelle année a été créé la première photographie numérique?"},{"radio":[{"label":"1839","sol":false},{"label":"2001","sol":false},{"label":"1909","sol":false},{"label":"1957","sol":true}]}],[{"chrono":45},{"text":"En quelle année a été créé le premier capteur de photo numérique (CCD)?"},{"radio":[{"label":"1839","sol":false},{"label":"2001","sol":false},{"label":"1909","sol":false},{"label":"1969","sol":true}]}],[{"chrono":45},{"text":""},{"radio":[{"label":"photons","sol":false},{"label":"photomatons"},{"label":"photosensors","sol":false},{"label":"photosites","sol":true}]}],[{"chrono":45},{"text":"En quelle année a été créé le premier appareil photo numérique portable?"},{"radio":[{"label":"1839","sol":false},{"label":"2001","sol":false},{"label":"1909","sol":false},{"label":"1975","sol":true}]}],[{"chrono":45},{"text":"En quelle année a été créé les premiers téléphones mobiles avec un appareil photo numérique?"},{"radio":[{"label":"1839","sol":false},{"label":"2000","sol":true},{"label":"2010","sol":false},{"label":"1957","sol":false}]}],[{"chrono":45},{"text":"Quel type de photo faut-il utiliser pour faire du traitement d'image? "},{"radio":[{"label":"Photo numérique","sol":true},{"label":"Photo argentique","sol":false},{"label":"Photo imprimée","sol":false}]}],[{"chrono":45},{"text":""},{"radio":[{"label":"en binaire","sol":true},{"label":"sous forme de texte","sol":false},{"label":"sous forme de couleur","sol":false}]}],[{"chrono":45},{"text":"C'est quoi la définition d'une image?"},{"radio":[{"label":"C'est le nombre de pixels","sol":true},{"label":"C'est la surface de l'image.","sol":false},{"label":"C'est le nombre de couleurs","sol":false},{"label":"C'est la taille d'un pixel","sol":false}]}],[{"chrono":45},{"text":"C'est quoi la résolution d'une image?"},{"radio":[{"label":"C'est le nombre de pixels","sol":false},{"label":"C'est la surface de l'image.","sol":false},{"label":"C'est le nombre de couleurs","sol":false},{"label":"C'est la taille d'un pixel","sol":true}]}],[{"chrono":45},{"text":"Combien y a t-il de couleurs possibles pour une image numérique?"},{"radio":[{"label":"environ 16 millions","sol":true},{"label":"environ 16 mille","sol":false},{"label":"environ 16 cents","sol":false},{"label":"environ 16 milliards","sol":false}]}],[{"chrono":45},{"text":""},{"radio":[{"label":"rgb(0,0,0)","sol":false},{"label":"rgb(255,255,255)","sol":true},{"label":"rgb(255,0,0)","sol":false},{"label":"rgb(130,130,130)","sol":false}]}],[{"chrono":45},{"text":""},{"radio":[{"label":"rgb(0,0,0)","sol":false},{"label":"rgb(255,255,255)","sol":false},{"label":"rgb(255,0,0)","sol":true},{"label":"rgb(130,130,130)","sol":false}]}],[{"chrono":45},{"text":""},{"radio":[{"label":"rgb(0,0,0)","sol":false},{"label":"rgb(255,255,255)","sol":false},{"label":"rgb(255,0,0)","sol":false},{"label":"rgb(130,130,130)","sol":true}]}],[{"chrono":45},{"text":""},{"radio":[{"label":"le pixel","sol":true},{"label":"le point","sol":false},{"label":"le mètre","sol":false},{"label":"le photon","sol":false}]}],[{"chrono":45},{"text":""},{"radio":[{"label":"255","sol":false},{"label":"256","sol":true},{"label":"3","sol":false},{"label":"plus de 16 millions.","sol":false}]}]]

Détails

Écrit par : Richard GAUTHIER

Création : 24 Novembre 2019

Mis à jour : 24 Novembre 2019

Clics : 1432