Supposons que l'on cherche à déterminer si deux tableaux d'entiers contiennent exactement les mêmes éléments, avec pour chacun le meme 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 pourrait é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.
Si en revanche les deux tableaux se trouvent être triés, par exemple par ordre croissant, la comparaison devient beaucoup plus facile.
II suffit de verifier que les valeurs contenues aux mêmes indices sont les mêmes.
Le programme ci-dessous réalise une telle comparaison, en s'arrêtant des que la comparaison échoue. II est donc facile de comparer le contenu de deux tableaux si on peut les trier.
C'est justement le problème du tri que nous allons aborder dans cette séquence, avec deux algorithmes différents pour trier un tableau.
La fonction suivante compare deux tableaux
def compare_tableaux(t, u):
\"\"\"compare deux tableaux de meme longueur, supposes tries\"\"\"
for i in range(len(t)):
if t[i] != u[i] :
return False
return True
Ecrire et tester le programme avec les instruction suivantes :
ab1 = [1,1,2,3]
tab2 = [1,2,2,4]
tab3 = [1,1,2,3]
print(\"compare tab1 et tab2 ; \", compare_tableaux(tab1,tab2))
print(\"compare tab1 et tab3 ; \", compare_tableaux(tab1,tab3))
Ecrire le résultat ici.
Le tri possède d'innombrables applications. Une fois que des données sont triées, il est très rapide de, déterminer :
- la médiane,
- si une valeur donnée est présente,
- quelle est la valeur la plus fréquente
-, etc.
Le t.ri est également un ingrédient. de base de nombreux algorithmes.
On pe.ut compare:
- le contenu de deux tableaux sans les trier.
L'idée est de compter les nombres d'occurrences de chaque valeur. Si on le fait avec une double boucle, la complexité sera quadratique (proportionnelle au carré de la longueur des tableaux).
Mais on peut le faire plus subtilement en construisant pour chaque tableau un dictionnaire donnant pour chaque valeur son nombre d'occurrences.
Il ne reste plus alors qu'a comparer le contenu des deux dictionnaires. Celle fois, Ia complexité est linéaire (proportionnelle à ia longueur des tableaux).
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 = [ 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 à gauche de la partie non triée.
Ainsi, la première é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.
Par construction, la partie gauche déjà triée ne contient que des éléments inférieurs ou égaux à ceux de la partie droite restant à trier.
On commence par se donner une fonction echange pour échanger les deux éléments d'un tableau t situés aux indices i et j.
def echange(t , i, j ) :
tmp = t[i]
t[i] = t[j]
t[j] = tmp
Ecrire et tester la fonction avec les instructions suivantes :
tab = [6,5,8,5,7,10,9,6,1,4,2,3,2]
print(\"depart\",tab)
echange(tab,0,8)
print(\"echange case 0 avec 8\",tab)
Comme on le voit, la fonction echange se sert d'une variable temporaire tmp pour stocker la valeur t[i] , remplace alors t[i] par t[j], puis enfin remplace t[j] par l'ancienne valeur de t[i] contenue dans tmp.
Ecrire ici le résultat.
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)):
Comme nous l'avons expliqué plus haut, la partie déjà examinée du tableau est supposée déjà triée.
Il convient de faire un petit dessin pour bien visualiser la situation :
0 i
t = [ déjà trié , pas encore trié ]
Sur ce dessin, on materialise bien le fait que l'élément d'indice i n'est pas encore examiné et ne fait donc pas partie des éléments déjà triés.
En particulier, à la première itération de la boucle, i vaut 0 et la partie gauche est donc vide.
En réalité, il faudrait être plus précis encore, en indiquant que la partie gauche déjà triée contient des éléments tous plus petits que la partie droite non encore triée.
0 i
t = [ déjà trié , elements plus grands non tries ]
C'est là notre invariant de boucle.
Ii faut maintenant chercher le plus petit élément dans la partie droite, c'est-à-dire la partie du tableau allant des indices i à len(t) -1 inclus.
Pour cela, on va écrire une boucle pour parcourir cette partie du tableau et on va se servir d'une variable m pour retenir l'indice de la plus petite valeur rencontrée.
m = i
for j in range(i + 1, len(t)):
if t[j] < t[m]:
m = j
La variable m est initialisée avec i, c'est-à-dire l'indice de la première valeur examinée.
Puis la boucle considère tous les indices de i+1 à len(t)-1, avec une variable j et, met à jnur m si une valeur est plus petite que t[m] est trouvée.
Maintenant, il nous reste plus qu'à écrire le programme complet du tri par sélection :
def tri_par_selection(t) :
\"\"\"trie le tableau t dams l'ordre croissant\"\"\"
for i in range(len(t)):
# t[0 , i [ est trié et <= a t[i , ...]
# on cherche le minimum de t[i , ...]
m = i
for j in range(i + 1, len(t)):
if t[j] < t[m]:
m = j
echange(t, i, m)
Ecrire et tester le fonction avec les instruction suivantes:
tab = [6,5,8,5,7,10,9,6,1,4,2,3,2]
print(\"depart\",tab)
tri_par_selection(tab)
print(\"tab triè\",tab)
Une fois que l'on est sortie de cette boucle, on a donc trouvé la position m de la plus petite valeur de la partie droite. Ii ne reste donc plus qu'à effectuer l'échange des valeurs aux indices i et m, avec notre fonction echange, ce qui achève notre tri par sélection.
Ecrire ici le résultat.
"}],[{"text":"Il est légitime de se demander si c'est là une manière efficace de trier un tableau.
Nous allons vois combien de temps met notre tri par sélection pour trier un tableau de mille éléments, d'un million d'éléments, ou plus encore?
Réalisons donc cette expèrience : pour plusieurs tailles différentes, construisons un tableau contenant des valeurs aléatoires (avec une loi uniforme, par exemple) puis mesurons le temps d'exécution de notre tri par sélection sur ce tableau.
import time
import random
taille = 100
tab = [int(random.uniform(0,100)) for i in range(taille)]
print(tab)
tpsdep = time.time()
tri_par_selection(tab)
tpsfin = time.time()
temps = tpsfin - tpsdep
print(\"temps de calcul\",temps)
Compléter le tableau ci-dessous en changeant la taille de tab.
Dessiner la courbe correspondante.
Analiser la courbe.
Compléter le tableau :
| taille | 1000 | 2000 | 4000 | 8000 | 16000 |
| temps (s) |
Copier la courbe ici.
Comme on le voit, le temps de calcul augmente rapidement avec la taille du tableau.
On en est déjà a presque 7 secondes pour trier 16 000 éléments.
En particulier, ii y a peu d'espoir de pouvoir trier ainsi des tableaux contenant des millions d'éléments.
Si on regarde les temps de calcul plus attentivement, on observe également que le temps de calcul n'augmente pas proportionnellement à la taille du tableau. En effet, pour un tableau deux fois plus grand, il semble qu'il faille plus que deux fois plus de temps pour le trier.
Le rapport semble même s'approcher de quatre plutôt que de deux.
On peut expliquer ainsi ce phénomène. Dans sa première étape, le tri par sélection parcourt tout le tableau à la recherche de la plus petite valeur, ce qui prend un temps proportionnel à la taille du tableau.
Appelons n cette taille.
Dans la deuxième étape, on parcourt n - 1 cases du tableau à la recherche du plus petit élément, puis n — 2 cases dans l'étape suivante, et ainsi de suite jusqu'à 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 + ••• + 1
calculs élémentaires. Il se trouve que 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 précédent.
Nous allons essayer d'améliorer (un peu) les choses avec un second algorithme de tri.
Un autre algorithme de tri, souvent utilisé par les joueurs de cartes, est le tri par insertion.
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 :
t = [ 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 inserer la première valeur non encore triée, c'est-a-dire la valeur la plus à gauche dans la partie droite non triée, dans la partie gauche déjà triée.
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é.
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[i], en supposant
que les valeurs t[0] , ... , t[i-1] sont triées, ce que l'on peut illustrer ainsi :
0 i
t = [ déjà trié, ? ,pas encore trié ]
Comme on l'a expliqué plus haut, 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 i
t = [ déjà trié, v ,déjà trié , pas encore trié ]
Dans un cas extrôme, la valeur v est plus grande que toutes les autres et on aura j = i.
Dans l'autre cas extrême, elle est au contraire plus petite que toutes les autres et on aura j = 0. La fonction insere s'ecrit avec une boucle while, dont le code est le suivant :
def insere(t , i , v) :
\"\"\"insere v dans t[O. i[ supposé trié\"\"\"
j = i
while j > 0 and t[j - 1] > v:
t[j] = t[j - 1]
j = j - 1
t[j] = v
Ecrire le code et le tester avec les instructions suivantes:
tab = [5, 5, 6, 6, 7, 8, 9, 10, 1, 4, 2, 3, 2]
print(\"depart tab=\",tab)
insere(t , 8 , 1)
print(\"après insere de 1 dans case 8 tab=\",tab)
Vous prendrez le temps de bien lire et de bien comprendre le code de la fonction insere.
Ii est plus subtil qu'il n'y parait. En particulier, il é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 . . . et a la paresse de l'évaluation du and.
Ainsi, lorsque j atteint la valeur 0, le test j > 0 échoue et le programme ne tente pas d'accéder a t[j - 1], ce qui serait incorrect.
Ecrire et commenter ici les résultats.
Le plus dur est fait. Pour écrire le 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, dont le code est le suivant;
def tri_par_insertion(t):
\"\"\"trie du tableau t dans l'ordre croissant\"\"\"
for i in range(1, len(t)):
# invariant : t[O . i[ est trié
print(t , i, t[i])
insere(t , i, t[i])
Ecrire et tester le code avec les instructions suivantes:
tab = [6,5,8,5,7,10,9,6,1,4,2,3,2]
print(\"depart tab=\",tab)
tri_par_insertion(tab)
print(\"trié par insertion tab=\",tab)
Ii est important de faire remarquer qu'un appel à insere(t , i, v) supprime du tableau t la valeur t[i] et y insàre 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], justement, ce qui garantit bien une permutation des éléments du tableau.
Ecrire et commenter ici les résultats.
Dans le pire des cas, le tri par insertion n'est pas meilleur que le tri par sélection. Ii 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 sont déjà trié et examinons ce qui se passe. à chaque appel de la fonction insere, la valeur v se trouve être supérieure ou égale à la première valeur à laquelle elle est comparée (à 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 consequent, le tri par insertion se limite n appels a la fonction insere qui prennent tous un temps constant, d'où 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é"},{"edit":" "}],[{"text":"Dans nos deux programmes de tri par sélection et. par insertion, on a supposé que I'on triait des tableaux d'entiers et on a utilisé la comparaison des entiers fournie par Pyth (à savoir les opérations < et >, respectivement).
Mais on pourrait tout aussi bien trier des valeurs qui ne sont pas des entiers, par exemple des chaînes de caractères, ou encore trier des entiers autrement que par ordre croissant. Il suffirait pour cela de remplacer les opérations < et > de Python dans nos programmes par un appel à une fonction indiquant si deux éléments sont bien ordonnés.
Pour trier un tableau contenant N valeurs, nous avons vu que nos deux algorithmes de tri, par sélection et par insertion, peuvent prendre un temps proportionnel à N2 dans le pire des cas. Peut-on espérer faire mieux et quelle est la limite que l'on peut espérer obtenir?
Si on suppose qu'on ne connait rien quant aux valeurs à trier, notamment leur distribution, et qu'on peut seulement les comparer deux à deux, alors Ia théorie nous indique qu'il faut au moins N.log2( N ) comparaisons, dans le pire des cas, pour trier N valeurs.
La fonction mathématique log2, appelée logarithme, croit relativement lentement (comme le nombre de chiffres nécessaires pour écrire son argument ).
Par exemple, si nous avons 1 milliard ( 109 ) élément à trier, nous aurons log2(109) < 30 .
Il existe plusieurs algorithmes qui réalisent cette borne inférieure (le tri par tas et le tri par fusion ).
Si en revanche on possède une information quant à la nature ou la distribution des valeurs, on peut faire encore mieux.
Si par exemple on possède l'information qu'il n'y a que sept valeurs différentes, ou encore qu'il s'agit d'entiers compris entre -231 et 231, alors on peut trier N valeurs en un temps proportionnel à N.
Le tri par dénombrement en est un exemple .
","title":"A quelle vitesse peut-on espérer trier? "},{"edit":" "}],[{"text":"Python fournit des fonctions pour trier des tableaux, plus efficaces que les tris par sélection et par insertion.
Elles se présentent de deux manières différentes, 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.
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 = [6,5,8,5,7,10,9,6,1,4,2,3,2]
print(\"depart tab=\",tab)
tabtrier = sorted(tab)
print(\"trié par sorted\",tab1)
print(\"fin tab=\",tab)
Ecrire et tester le code ci-dessous.
Comme on le voit, le tableau t n'a pas été modifié.
Par contre t.sort() , en revanche, modifie le tableau t pour le trier, sans rien renvoyer.
tab = [6,5,8,5,7,10,9,6,1,4,2,3,2]
print(\"depart tab=\",tab)
tab.sort()
print(\"trié par sort\",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é.
import time
import random
taille = 16000
tab = [int(random.uniform(0,100)) for i in range(taille)]
print(tab)
tpsdep = time.time()
tab.sort()
tpsfin = time.time()
temps = tpsfin - tpsdep
print(\"temps de calcul\",temps)
Ecrire et tester le code.
Ecrire et commenter ici les résultats.
def compare_tableaux(t, u):
\"\"\"compare deux tableaux de meme longueur, supposes tries\"\"\"
for i in range(len(t)):
if t[i] != u[i] :
return False
return True
tab1 = [1,1,2,3,4]
tab2 = [1,2,2,4]
tab3 = [1,1,2,3]
print(\"compare tab1 et tab2 ; \", compare_tableaux(tab1,tab2))
print(\"compare tab1 et tab3 ; \", compare_tableaux(tab1,tab3))
Améliorer la fonction compare pour traiter le cas général de deux tableaux n'ayant pas forcement la mêrne taille.
En supposant que le tri par sélection prend un temps directement proportionnel à N2 et qu'il prend 6,8 secondes pour trier 16 000 valeurs, calculer le temps qu'il faudrait pour trier un million de valeurs avec ce mêrne tri par sélection.
Détailler les différentes étapes du tri par sélection sur le tableau :
t = [ 3 , 4 , 1 , 7 , 2 ]
Dans la toute dernière étape du tri par sélection, ii n'y a qu'une seule valeur dans la partie droite et il est donc inutile d'y chercher la plus petite valeur ni de l'échanger avec elle-même. Modifier le programme tri par sélection pour éviter cette étape inutile.
Détailler les différentes étapes du programme tri par insertion sur le tableau
t = [ 3 , 4 , 1 , 7 , 2 ]
","title":"Exercice 5"},{"edit":" "}],[{"text":"Que se passe-t-il lorsque le tri par insertion est appliqué à un tableau qui se présente en ordre croissant?
Ecrire une fonction est_trie(t) qui renvoie True si le tableau t est trié par ordre croissant et False sinon.
","title":"Exercice 7"},{"edit":" "}],[{"text":"Ecrire une fonction plus_petits qui prend en paramètres un tableau t et un entier k suppose inférieur à la longueur de t et qui renvoie un tableau contenant, dans l'ordre, les k plus petits éléments de t.
Vous pourrez vous servir de la fonction insere.
","title":"Exercice 8"},{"edit":" "}],[{"text":"Ecrire une fonction 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
t = [0,2,2,3,6,6,6]
histo(t) donne :
1 fois 0
2 fois 2
1 fois 3
3 fois 6
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.
t = [0,2,2,3,6,6,6]
freq(t) donne :
6
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.
t = [1,0]
tri_deux_valeurs(t)
print(t) donne :
t = [0,1]
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 ou nuls et plus petits qu'une constante max donnée (par exemple 100).
Ecrire une fonction tri_par_denombrement qui réalise cet algorithme.
","title":"Exercice 12"},{"edit":" "}]]