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