PROJET 2
AUTOMATISATION DES MESURES DE DURÉE D'UN TRI
En informatique, un algorithme de tri permet d'organiser et donc de trier par ordre croissant, des listes avec des valeurs non triées.
-
L'idée du projet Durée d'un tri est de rendre automatique la mesure de durée d'exécution d'un algorithme de tri, de manière à ensuite comparer l'efficacité des différents types de tris
Pour ce faire, nous avons tout d'abord étudié en classe plusieurs algorithmes de tri tels que le tri par insertion, le tri par sélection, le tri à bulles ou encore le tri par fusion, entre autres. Par la suite, et avec la connaissance de ces codes comme bagage, nous avons dû élaboré un protocole nous permettant de comparer la durée d'exécution de chacun de ces tris. Le protocole étant quelque peu complexe car il devait inclure des prises de mesures de manière à ensuite calculer une moyenne, nous nous sommes alors dirigés vers la création d'un programme qui pourrait automatiser ces mesures. Il faut également savoir que la durée d’exécution d'un tri, pour un nombre d'élément donné, est différent à chaque essai. Ce projet est ainsi intéressant car il nous permettra d'obtenir un résultat statistiquement satisfaisant de ces durées.
22/11/23
Aujourd'hui, nous terminons l'élaboration du programme de mesure de durée du tri sort, sorted, par insertion, et par sélection, à partir d'une liste aléatoire. Mon programme fonctionne et affiche des durées réalistes pour chaque tris. Cela me semble alors être correct. Ensuite, notre professeur nous fournit une correction possible de ce programme. Je peux ainsi comparer cette correction avec mon travail préalablement rédigé. Je suis alors rassurer car ce programme qui représente la base du projet, est effectivement correct.
La rédaction de ce code d'automatisation n'était en soit pas réellement complexe. Nous avons utilisé la bibliothèque random puis créer cinq listes différentes soient une liste n qui est le nombre d'éléments à trier ainsi que quatre listes sous le modèle: duree_tri[], et ce pour les quatre tris dont nous allons étudier les durées.
Ce programme se trouve ci-dessous:
import random
n=[100,1000,5000,8000,10000]
duree_insertion=[]
duree_selection=[]
duree_sort=[]
duree_sorted=[]
def creation_liste_aleatoire(n):
liste = []
for k in range(n):
liste.append(random.randint(0,100))
return liste
def duree_tri_sort(liste):
t1=time()
liste.sort()
t2=time()
duree=t2-t1
#print("Tri sort, durée = " ,duree)
duree_sort.append(duree)
random.shuffle(liste)
def duree_tri_sorted(liste):
t1=time()
liste2=sorted(liste)
t2=time()
duree=t2-t1
#print("Tri sorted, durée = " ,duree)
duree_sorted.append(duree)
random.shuffle(liste)
def duree_tri_insertion(A):
t1=time()
for j in range (1,len(A)):
key=A[j]
i=j-1
while i>=0 and A[i]>key:
A[i+1]=A[i]
i=i-1
A[i+1]=key
t2=time()
duree=t2-t1
#print("Tri par insertion, durée = " ,duree)
duree_insertion.append(duree)
random.shuffle(liste)
def duree_tri_selection(A):
t1=time()
for i in range (len(A)):
min = i
for j in range(i+1, len(A)):
if A[min]>A[j]:
min=j
tmp=A[i]
A[i]=A[min]
A[min]=tmp
t2=time()
duree=t2-t1
#print("Tri par sélection, durée = " ,duree)
duree_selection.append(duree)
random.shuffle(liste)
for element in n:
liste= creation_liste_aleatoire(element)
print(element)
duree_tri_insertion(liste)
duree_tri_selection(liste)
duree_tri_sort(liste)
duree_tri_sorted(liste)
Après cette première étape terminée, notre professeur nous donne une nouvelle consigne. En effet, nous devons à présent modifier ce programme de manière à obtenir un graphique qui donnerait les durées d’exécution des tris, en fonction du nombre d'éléments à trier.
Pour ce faire, je m'inspire du programme que j'avais utilisé pour le Projet PIX. Le but final de ce projet étant de tracer un graphique, je reprends la base du code.
Ceci sont les morceaux du code dont nous aurons précisément besoin. A présent, adaptons-le à notre programme.
Pour cela, notre professeur nous indique la structure que doit prendre le tracé de chaque durée de tri.
En ordonnée, je place n qui est le nombre d'éléments à trier puis en abscisse, les durées.
Après avoir appelé chaque fonction et terminé d'adapter le code, je me retrouve avec ce programme:
Je suis assez sure de mon code car sa rédaction n'était en soit pas si complexe, alors je l’exécute. Néanmoins, après l’exécution, cette erreur s'affiche dans la console:
J'avoue avoir pris un peu trop de temps à comprendre d'où cette erreur venait. Finalement, j'avais simplement oublié d'importer la bibliothèque matplotlib. J'ai dû en toute honnêteté perdre cinq minutes à réfléchir à pourquoi mon code ne marchait pas. Enfin bref, nous dirons que j'étais fatiguée aujourd'hui.
Donc après avoir compris la stupidité de mon erreur, je rajoute l'importation de la bibliothèque matplotlib, de cette manière:
Mon code fonctionne étrangement à présent. Voici alors le programme final ainsi que le résultat de son exécution.
import matplotlib.pyplot as plt
def tracer_figure(liste_noms,liste_scores):
plt.figure(figsize = (16, 10))
plt.bar(liste_noms,liste_scores, label='Notes')
plt.xlabel('Noms')
plt.xticks(rotation = 60)
plt.ylabel('Notes')
plt.title("Notation Pix")
plt.legend()
plt.show()
tracer_figure(liste_noms,liste_scores)
for element in n:
liste= creation_liste_aleatoire(element)
print(element)
duree_tri_insertion(liste)
duree_tri_selection(liste)
duree_tri_sort(liste)
duree_tri_sorted(liste)
def tracer_figure(duree_sort,duree_sorted,duree_insertion,duree_selection,n):
plt.figure(figsize = (16, 10))
plt.plot(n,duree_sort,"o", color='pink', label = 'sort', marker="+")
plt.plot(n,duree_sorted,"o", color='purple', label= 'sorted', marker="x")
plt.plot(n,duree_insertion,"o", color='red', label= 'insertion', marker="1")
plt.plot(n,duree_selection,"o", color='grey', label= 'selection', marker="2")
plt.xlabel('n')
plt.ylabel('Durées')
plt.title("Durées automatisation tris")
plt.legend()
plt.grid(True)
plt.show()
tracer_figure (duree_sort,duree_sorted,duree_insertion,duree_selection,n)
Traceback (most recent call last):
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Automatisation durée tris graphique.py", line 102, in <module>
tracer_figure (duree_sort,duree_sorted,duree_insertion,duree_selection,n)
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Automatisation durée tris graphique.py", line 88, in tracer_figure
plt.figure(figsize = (16, 10))
NameError: name 'plt' is not defined
import matplotlib.pyplot as plt
import random
from time import *
import matplotlib.pyplot as plt
n=[100,1000,5000,8000,10000]
duree_insertion=[]
duree_selection=[]
duree_sort=[]
duree_sorted=[]
def creation_liste_aleatoire(n):
liste = []
for k in range(n):
liste.append(random.randint(0,100))
return liste
def duree_tri_sort(liste):
t1=time()
liste.sort()
t2=time()
duree=t2-t1
#print("Tri sort, durée = " ,duree)
duree_sort.append(duree)
random.shuffle(liste)
def duree_tri_sorted(liste):
t1=time()
liste2=sorted(liste)
t2=time()
duree=t2-t1
#print("Tri sorted, durée = " ,duree)
duree_sorted.append(duree)
random.shuffle(liste)
def duree_tri_insertion(A):
t1=time()
for j in range (1,len(A)):
key=A[j]
i=j-1
while i>=0 and A[i]>key:
A[i+1]=A[i]
i=i-1
A[i+1]=key
t2=time()
duree=t2-t1
#print("Tri par insertion, durée = " ,duree)
duree_insertion.append(duree)
random.shuffle(liste)
def duree_tri_selection(A):
t1=time()
for i in range (1,len(A)):
min = i
for j in range(i+1, len(A)):
if A[min]>A[j]:
min=j
tmp=A[i]
A[i]=A[min]
A[min]=tmp
t2=time()
duree=t2-t1
#print("Tri par sélection, durée = " ,duree)
duree_selection.append(duree)
random.shuffle(liste)
for element in n:
liste= creation_liste_aleatoire(element)
print(element)
duree_tri_insertion(liste)
duree_tri_selection(liste)
duree_tri_sort(liste)
duree_tri_sorted(liste)
def tracer_figure(duree_sort,duree_sorted,duree_insertion,duree_selection,n):
plt.figure(figsize = (16, 10))
plt.plot(n,duree_sort,"o", color='pink', label = 'sort', marker="+")
plt.plot(n,duree_sorted,"o", color='purple', label= 'sorted', marker="x")
plt.plot(n,duree_insertion,"o", color='red', label= 'insertion', marker="1")
plt.plot(n,duree_selection,"o", color='grey', label= 'selection', marker="2")
plt.plot(n,duree_bulles,"o", color='green', label= 'bulles', marker="3")
plt.xlabel('n')
plt.ylabel('Durées')
plt.title("Durées automatisation tris")
plt.legend()
plt.grid(True)
plt.show()
tracer_figure (duree_sort,duree_sorted,duree_insertion,duree_selection,n)
24/11/23
Lors de cette séance de cours, nous commençons à travailler sur un nouvel aspect du projet. Nous devons effectivement programmer deux à trois nouveaux algorithmes de tris et calculer leur durée d'exécution. Je décide de commencer avec le tri à bulles. Je pense par la suite faire le tri par fusion et peut-être le tri rapide.
Pour ce faire, je commence par reprendre le modèle des tris précèdent que notre professeur nous avaient donnés. C'est-à-dire que je crée d'abord une fonction duree_tri_bulles qui prend la liste liste comme argument.
Puis, je crée une boucle avec i qui prend toute les valeurs de la liste liste. Pour continuer mon code, je décide de me documenter. Sur le site Libre cours dans la rubrique "Quelques algorithmes classiques" (https://librecours.net/module/js/js04/tri.xhtml), je trouve de quoi avancer sur mon programme. Il en est de même avec le site WayToLearnX qui me permet également de mieux comprendre le tri à bulles (https://waytolearnx.com/2019/04/tri-a-bulle-en-python.html). Ma documentation ayant portée ses fruits, je réussi à adapter mes recherches à mon programme. Aussi, j'ai trouvé que le tri à bulles était un algorithme assez simple à coder car le principe n'est pas compliqué. Il suffit de parcourir l'ensemble de la liste et si une valeur est supérieure à la précédente, elles inversent leur place.
Ensuite, je termine par rajouter de quoi mesurer la durée d’exécution de ce tri. Ci-dessous, j'ai comparé la fonction du tri par insertion avec celle du tri à bulles pour que vous puissiez remarquer les similitudes.
def duree_tri_insertion(A):
t1=time()
for j in range (1,len(A)):
key=A[j]
i=j-1
while i>=0 and A[i]>key:
A[i+1]=A[i]
i=i-1
A[i+1]=key
t2=time()
duree=t2-t1
#print("Tri par insertion, durée = " ,duree)
duree_insertion.append(duree)
random.shuffle(liste)
def duree_tri_bulles(liste):
t1=time()
for i in range (len(A)):
for j in range(len(A)-1-i):
print(A)
pb = A[j]
if A[j+1] <= A[j]:
A[j] , A[j+1] = A[j+1] , A[j]
t2=time()
duree=t2-t1
#print("Tri à bulles, durée = " ,duree)
duree_bulles.append(duree)
random.shuffle(liste)
Je ne rencontre pas de difficulté spéciale lors de l'exécution. Je peux alors adapter l’ensemble de mon code avec ce nouvel algorithme.
import random
from time import *
import matplotlib.pyplot as plt
n=[100,1000,5000,8000,10000]
duree_insertion=[]
duree_selection=[]
duree_sort=[]
duree_sorted=[]
duree_bulles=[]
def creation_liste_aleatoire(n):
liste = []
for k in range(n):
liste.append(random.randint(0,100))
return liste
def duree_tri_sort(liste):
t1=time()
liste.sort()
t2=time()
duree=t2-t1
#print("Tri sort, durée = " ,duree)
duree_sort.append(duree)
random.shuffle(liste)
def duree_tri_sorted(liste):
t1=time()
liste2=sorted(liste)
t2=time()
duree=t2-t1
#print("Tri sorted, durée = " ,duree)
duree_sorted.append(duree)
random.shuffle(liste)
def duree_tri_insertion(A):
t1=time()
for j in range (1,len(A)):
key=A[j]
i=j-1
while i>=0 and A[i]>key:
A[i+1]=A[i]
i=i-1
A[i+1]=key
t2=time()
duree=t2-t1
#print("Tri par insertion, durée = " ,duree)
duree_insertion.append(duree)
random.shuffle(liste)
def duree_tri_selection(A):
t1=time()
for i in range (1,len(A)):
min = i
for j in range(i+1, len(A)):
if A[min]>A[j]:
min=j
tmp=A[i]
A[i]=A[min]
A[min]=tmp
t2=time()
duree=t2-t1
#print("Tri par sélection, durée = " ,duree)
duree_selection.append(duree)
random.shuffle(liste)
def duree_tri_bulles(A):
t1=time()
for i in range (len(A)):
for j in range(len(A)-1-i):
print(A)
pb = A[j]
if A[j+1] <= A[j]:
A[j] , A[j+1] = A[j+1] , A[j]
t2=time()
duree=t2-t1
#print("Tri à bulles, durée = " ,duree)
duree_bulles.append(duree)
random.shuffle(liste)
for element in n:
liste= creation_liste_aleatoire(element)
print(element)
duree_tri_insertion(liste)
duree_tri_selection(liste)
duree_tri_sort(liste)
duree_tri_sorted(liste)
duree_tri_bulles(liste)
def tracer_figure(duree_sort,duree_sorted,duree_insertion,duree_selection,duree_bulles,n):
plt.figure(figsize = (16, 10))
plt.plot(n,duree_sort,"o", color='pink', label = 'sort', marker="+")
plt.plot(n,duree_sorted,"o", color='purple', label= 'sorted', marker="x")
plt.plot(n,duree_insertion,"o", color='red', label= 'insertion', marker="1")
plt.plot(n,duree_selection,"o", color='grey', label= 'selection', marker="2")
plt.plot(n,duree_bulles,"o", color='green', label= 'bulles', marker="3")
plt.xlabel('n')
plt.ylabel('Durées')
plt.title("Durées automatisation tris")
plt.legend()
plt.grid(True)
plt.show()
tracer_figure (duree_sort,duree_sorted,duree_insertion,duree_selection,duree_bulles,n)
01/12/23
Aujourd'hui, je décide de commencer à coder le tri par fusion (j'étais encore bien naïve car je ne me doutais pas que cela ne serait pas sans repos).
Comme je l'avais fait pour le tri à bulles, je commence mon travail par de la documentation. Rapidement, je perds le fil. En effet, je ne comprends pas comment coder ce tri car il nécessite deux listes. Néanmoins, je n'ai qu'une liste de valeurs. Il me semblait également que le principe du tri par fusion était de deviser en deux moitiés une seule liste non triée. Je ne comprends pas comment faire.
Je continue tout de même de me documenter mais fait face à de nombreux échecs car mes codes n'ont simplement aucun sens.
Finalement, j'arrive à me retrouver avec un algorithme de ce type:
def tri_fusion(liste):
if len(liste) == 1 or len(liste) == 0:
return liste
n = len(liste)//2
r = liste[:(len(liste)//2)]
l = liste[(len(liste)//2):]
return fusion(tri_fusion(l),tri_fusion(r))
"""
i, j, k = 0, 0, 0
while i < len(l)-1 and j < len(r)-1:
if l[i] < r[j]:
liste[k] = l[i]
i += 1
else:
liste[k] = r[j]
j +=1
k += 1
while i < len(l)-1:
liste[k] = l[i]
i += 1
k += 1
while j < len(l)-1:
liste[k] = r[i]
j += 1
k += 1
"""
def fusion(L1,L2):
i,j=0,0
a = len(L1)
b = len(L2)
L_fusion = []
while i<a and j<b:
if L1[i] < L2[j]:
L_fusion.append(L1[i])
i += 1
else:
L_fusion.append(L2[j])
j += 1
while i<a:
L_fusion.append(L1[i])
i+=1
while j<b:
L_fusion.append(L2[j])
j+=1
return L_fusion
def duree_tri_fusion(A):
t1=time()
tri_fusion(liste)
t2=time()
duree=t2-t1
#print("Tri par fusion, durée = " ,duree)
duree_fusion.append(duree)
random.shuffle(liste)
La partie mise en commentaire est présente dans ce code car elle était dans un algorithme que j'avais trouvé sur un site. Néanmoins, je n'en comprends absolument pas l'utilité ou même le sens ici. J'ai tout de même décidé de la partager avec vous car je pense m'être énormément embêter à essayer de comprendre ces lignes là, qui m'ont d'ailleurs causé un certain nombre d'erreurs dans la console tel que:
Mais quand j'ai élaboré ce code, j’avais tout de même décidé de laisser ces lignes pour essayer de comprendre leur utilité dans cet algorithme de tri.
Il faut comprendre que je suis parvenue à cet algorithme de tri après avoir combiné énormément de recherche. Ces lignes de code sont le fruit d'une documentation considérable.
Même si finalement, après avoir compris les étapes du tri, sa rédaction n'était pas tant complexe que ça.
Traceback (most recent call last):
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 141, in <module>
duree_tri_fusion(liste)
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 126, in duree_tri_fusion
tri_fusion(liste)
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 84, in tri_fusion
tri_fusion(l)
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 84, in tri_fusion
tri_fusion(l)
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 84, in tri_fusion
tri_fusion(l)
[Previous line repeated 2 more times]
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 85, in tri_fusion
tri_fusion(r)
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 100, in tri_fusion
liste[k] = r[i]
IndexError: list index out of range
>>>
08/12/23
Sur le site Algorithmes de tri (https://e-nsi.forge.aeif.fr/tris/04_rapides/02_rapide/), je parvient à trouver une explication détaillée du tri rapide. Le protocole est simple alors je me lance. Je suis les étapes indiquées sans réelle difficultés. D'autant plus que la présentation visuelle du tri proposée en introduction m'a permis de comprendre davantage son fonctionnement. Ceci est l'explication fournie:
Voici le premier jet de mon code:
def duree_tri_rapide(liste):
t1=time()
pivot=liste[-1]
curseur=0
for i in range(len(liste)-1):
if liste[i] <= pivot:
liste[i] , liste[curseur] = liste[curseur] , liste[i]
curseur = curseur+1
liste[curseur] , liste[-1] = liste[-1] , liste[curseur]
duree_tri_rapide(liste[:curseur])
duree_tri_rapide(liste[curseur:])
t2=time()
duree=t2-t1
#print("Tri rapide, durée = " ,duree)
duree_bulles.append(duree)
random.shuffle(liste)
Je décide de l'exécuter avec une petite liste et en plaçant l'algorithme du graphique en commentaire pour aller plus vite. Néanmoins, une erreur s'affiche dans la console:
duree_tri_rapide(liste)
Traceback (most recent call last):
File "<interactive input>", line 1, in <module>
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 148, in duree_tri_rapide
duree_tri_rapide(liste[:curseur])
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 148, in duree_tri_rapide
duree_tri_rapide(liste[:curseur])
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 148, in duree_tri_rapide
duree_tri_rapide(liste[:curseur])
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 141, in duree_tri_rapide
pivot=liste[-1]
IndexError: list index out of range
>>>
Je pense alors à modifier certaines lignes en y ajoutant la méthode len(liste), en espérant que cela fonctionne.
def duree_tri_rapide(liste):
t1=time()
pivot=liste[len(liste)-1]
curseur=0
for i in range(len(liste)-1):
if liste[i] <= pivot:
liste[i] , liste[curseur] = liste[curseur] , liste[i]
curseur = curseur+1
liste[curseur] , liste[len(liste)-1] = liste[len(liste)-1] , liste[curseur]
duree_tri_rapide(liste[:curseur])
duree_tri_rapide(liste[curseur:])
t2=time()
duree=t2-t1
#print("Tri rapide, durée = " ,duree)
duree_rapide.append(duree)
random.shuffle(liste)
J'exécute mais cette fois, cette erreur survient dans la console:
Traceback (most recent call last):
File "<interactive input>", line 1, in <module>
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 150, in duree_tri_rapide
duree_tri_rapide(liste[:curseur])
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 150, in duree_tri_rapide
duree_tri_rapide(liste[:curseur])
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 151, in duree_tri_rapide
duree_tri_rapide(liste[curseur:])
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 151, in duree_tri_rapide
duree_tri_rapide(liste[curseur:])
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 151, in duree_tri_rapide
duree_tri_rapide(liste[curseur:])
[Previous line repeated 973 more times]
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 150, in duree_tri_rapide
duree_tri_rapide(liste[:curseur])
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 157, in duree_tri_rapide
random.shuffle(liste)
File "C:\Users\EduPython\App\lib\random.py", line 275, in shuffle
for i in reversed(range(1, len(x))):
RecursionError: maximum recursion depth exceeded in comparison
>>>
Je repère quelques modifications éventuelles que je pourrais apporter à mon code. Comme avec le tri par fusion, je divise l'algorithme en deux partie avec une fonction tri_rapide et une autre durée_tri_rapide. Je remarque également que je n'ai pas mis de condition à mon tri. Ainsi, j'ajoute que si la liste à trier ne contient pas d'élément ou même qu'un seul, le tri ne peut pas se faire. Néanmoins, ce message d'erreur signifie concrètement que la boucle fonctionne à l'infini, sauf que je ne comprend pas où je me suis trompée.
def tri_rapide(liste):
if len(liste)!=0 and len(liste)!=1:
pivot=liste[len(liste)-1]
curseur=0
for i in range(len(liste)-1):
if liste[i] <= pivot:
liste[i] , liste[curseur] = liste[curseur] , liste[i]
curseur = curseur+1
liste[curseur] , liste[len(liste)-1] = liste[len(liste)-1] , liste[curseur]
duree_tri_rapide(liste[:curseur])
duree_tri_rapide(liste[curseur:])
def duree_tri_rapide(liste):
t1=time()
tri_rapide(liste)
t2=time()
duree=t2-t1
#print("Tri rapide, durée = " ,duree)
duree_rapide.append(duree)
random.shuffle(liste)
Après son exécution, la console affiche de nouveau une erreur:
Traceback (most recent call last):
File "<interactive input>", line 1, in <module>
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 160, in duree_tri_rapide
tri_rapide(liste)
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 151, in tri_rapide
duree_tri_rapide(liste[:curseur])
File "D:\Clé\High school\11th grade\Subjects\NSI\TRI\Durée automatisation tri par fusion.py", line 164, in duree_tri_rapide
duree_rapide.append(duree)
NameError: name 'duree_rapide' is not defined
J'ajoute des print(liste) dans mon algorithme, en dehors et à l'intérieur même de la boucle, pour comprendre d'où vient cette erreur:
def tri_rapide(liste):
if len(liste)!=0 and len(liste)!=1:
print(liste)
pivot=liste[len(liste)-1]
curseur=0
for i in range(len(liste)-1):
print(liste)
if liste[i] <= pivot:
liste[i] , liste[curseur] = liste[curseur] , liste[i]
curseur = curseur+1
liste[curseur] , liste[len(liste)-1] = liste[len(liste)-1] , liste[curseur]
print(liste)
duree_tri_rapide(liste[:curseur])
duree_tri_rapide(liste[curseur:])
def duree_tri_rapide(liste):
t1=time()
tri_rapide(liste)
t2=time()
duree=t2-t1
#print("Tri rapide, durée = " ,duree)
duree_rapide.append(duree)
random.shuffle(liste)
Finalement, en remontant dans mon programme, je remarque que duree_rapide[] avait été auparavant mis en commentaire. En effet, comme je savais les tris que je souhaitais coder dès le départ, j'avais déjà crée la liste duree_rapide[] au début du programme mais l'avait mise en commentaire le temps que je code le tri à bulles puis par fusion. C'est erreur là n'est donc pas importante.
J'exécute alors de nouveau mon code mais il ne fonctionne toujours pas. En effet, voici ce qui s'affiche dans la console:
*** Remote Interpreter Reinitialized ***
>>> liste = [3,13,1056,4,56,26,72,1,2]
>>> duree_tri_rapide(liste)
[3, 13, 1056, 4, 56, 26, 72, 1, 2]
[3, 13, 1056, 4, 56, 26, 72, 1, 2]
[3, 13, 1056, 4, 56, 26, 72, 1, 2]
[3, 13, 1056, 4, 56, 26, 72, 1, 2]
[3, 13, 1056, 4, 56, 26, 72, 1, 2]
[3, 13, 1056, 4, 56, 26, 72, 1, 2]
[3, 13, 1056, 4, 56, 26, 72, 1, 2]
[3, 13, 1056, 4, 56, 26, 72, 1, 2]
[3, 13, 1056, 4, 56, 26, 72, 1, 2]
[1, 2, 1056, 4, 56, 26, 72, 3, 13]
[2, 1056, 4, 56, 26, 72, 3, 13]
[2, 1056, 4, 56, 26, 72, 3, 13]
[2, 1056, 4, 56, 26, 72, 3, 13]
[2, 1056, 4, 56, 26, 72, 3, 13]
[2, 4, 1056, 56, 26, 72, 3, 13]
[2, 4, 1056, 56, 26, 72, 3, 13]
[2, 4, 1056, 56, 26, 72, 3, 13]
[2, 4, 1056, 56, 26, 72, 3, 13]
[2, 4, 3, 13, 26, 72, 1056, 56]
[2, 4, 3]
[2, 4, 3]
[2, 4, 3]
[2, 3, 4]
[3, 4]
[3, 4]
[3, 4]
[13, 26, 72, 1056, 56]
[13, 26, 72, 1056, 56]
[13, 26, 72, 1056, 56]
[13, 26, 72, 1056, 56]
[13, 26, 72, 1056, 56]
[13, 26, 56, 1056, 72]
[13, 26]
[13, 26]
[13, 26]
[56, 1056, 72]
[56, 1056, 72]
[56, 1056, 72]
[56, 72, 1056]
[72, 1056]
[72, 1056]
[72, 1056]
>>>
Même en ajoutant un print(liste) à la fin de la boucle, il ne fonctionne pas. Je continue donc de travailler sur cet algorithme.
12/12/23
Je finalise aujourd'hui le projet. Voici le code final nous permettant de comparer les durées d'exécution des tris.
import random
from time import *
import matplotlib.pyplot as plt
n=[100,1000,5000,8000,10000]
duree_insertion=[]
duree_selection=[]
duree_sort=[]
duree_sorted=[]
duree_bulles=[]
duree_fusion=[]
duree_rapide=[]
def creation_liste_aleatoire(n):
liste = []
for k in range(n):
liste.append(random.randint(0,100))
return liste
def duree_tri_sort(liste):
t1=time()
liste.sort()
t2=time()
duree=t2-t1
#print("Tri sort, durée = " ,duree)
duree_sort.append(duree)
random.shuffle(liste)
def duree_tri_sorted(liste):
t1=time()
liste2=sorted(liste)
t2=time()
duree=t2-t1
#print("Tri sorted, durée = " ,duree)
duree_sorted.append(duree)
random.shuffle(liste)
def duree_tri_insertion(A):
t1=time()
for j in range (1,len(A)):
key=A[j]
i=j-1
while i>=0 and A[i]>key:
A[i+1]=A[i]
i=i-1
A[i+1]=key
t2=time()
duree=t2-t1
#print("Tri par insertion, durée = " ,duree)
duree_insertion.append(duree)
random.shuffle(liste)
def duree_tri_selection(A):
t1=time()
for i in range (1,len(A)):
min = i
for j in range(i+1, len(A)):
if A[min]>A[j]:
min=j
tmp=A[i]
A[i]=A[min]
A[min]=tmp
t2=time()
duree=t2-t1
#print("Tri par sélection, durée = " ,duree)
duree_selection.append(duree)
random.shuffle(liste)
def duree_tri_bulles(A):
t1=time()
for i in range (len(A)):
for j in range(len(A)-1-i):
print(A)
pb = A[j]
if A[j+1] <= A[j]:
A[j] , A[j+1] = A[j+1] , A[j]
t2=time()
duree=t2-t1
#print("Tri à bulles, durée = " ,duree)
duree_bulles.append(duree)
random.shuffle(liste)
def tri_fusion(liste):
if len(liste) == 1 or len(liste) == 0:
return liste
n = len(liste)//2
r = liste[:(len(liste)//2)]
l = liste[(len(liste)//2):]
return fusion(tri_fusion(l),tri_fusion(r))
def fusion(L1,L2):
i,j=0,0
a = len(L1)
b = len(L2)
L_fusion = []
while i<a and j<b:
if L1[i] < L2[j]:
L_fusion.append(L1[i])
i += 1
else:
L_fusion.append(L2[j])
j += 1
while i<a:
L_fusion.append(L1[i])
i+=1
while j<b:
L_fusion.append(L2[j])
j+=1
return L_fusion
def duree_tri_fusion(A):
t1=time()
tri_fusion(liste)
t2=time()
duree=t2-t1
#print("Tri par fusion, durée = " ,duree)
duree_fusion.append(duree)
random.shuffle(liste)
def tri_rapide(liste):
if len(liste)!=0 and len(liste)!=1:
print(liste)
pivot=liste[len(liste)-1]
curseur=0
for i in range(len(liste)-1):
print(liste)
if liste[i] <= pivot:
liste[i] , liste[curseur] = liste[curseur] , liste[i]
curseur = curseur+1
liste[curseur] , liste[len(liste)-1] = liste[len(liste)-1] , liste[curseur]
print(liste)
duree_tri_rapide(liste[:curseur])
duree_tri_rapide(liste[curseur:])
print(liste)
def duree_tri_rapide(liste):
t1=time()
tri_rapide(liste)
t2=time()
duree=t2-t1
#print("Tri rapide, durée = " ,duree)
duree_rapide.append(duree)
random.shuffle(liste)
for element in n:
liste= creation_liste_aleatoire(element)
print(element)
duree_tri_insertion(liste)
duree_tri_selection(liste)
duree_tri_sort(liste)
duree_tri_sorted(liste)
duree_tri_bulles(liste)
duree_tri_fusion(liste)
duree_tri_rapide(liste)
def tracer_figure(duree_sort,duree_sorted,duree_insertion,duree_selection,duree_bulles,duree_fusion,duree_rapiden):
plt.figure(figsize = (16, 10))
plt.plot(n,duree_sort,"o", color='pink', label = 'sort', marker="+")
plt.plot(n,duree_sorted,"o", color='purple', label= 'sorted', marker="x")
plt.plot(n,duree_insertion,"o", color='red', label= 'insertion', marker="1")
plt.plot(n,duree_selection,"o", color='grey', label= 'selection', marker="2")
plt.plot(n,duree_bulles,"o", color='green', label= 'bulles', marker="3")
plt.plot(n,duree_fusion,"o", color='blue', label= 'fusion', marker="4")
plt.plot(n,duree_rapide,"o", color='yellow', label= 'rapide', marker="5")
plt.xlabel('n')
plt.ylabel('Durées')
plt.title("Durées automatisation tris")
plt.legend()
plt.grid(True)
plt.show()
tracer_figure (duree_sort,duree_sorted,duree_insertion,duree_selection,duree_bulles,duree_fusion,duree_rapide,n)
.png)