novembre

Mois suivant

Voici un gros projet ce mois ci: On doit mesurer la durée d'exécution de différentes techniques de tris. Il y en a au départ 4 de celles étudiées précedemment:

-Le tri par sélection

-Le tri par insertion

-Le tri rapide "sort"

-Le tri rapide "sorted"

(On en rajoutera d'autres plus tard)

Attention! Vu que je m'y suis pris tard sur ce projet, je ne citerait pas les problèmes et bugs rencontés.

Mais c'est kwa le tri par:

Insertion?

Sélection ?

"Sort" ?

Bouh

Tout d'abord, il faut définir une liste n qui va stocker dans l'ordre le nombre d'éléments que l'on veut trier pour nos algorithmes. Une fois que c'est fait, on importe des tréfonds des abysses la fonction random, time(et plus précisément * pour pas s'embêter) et pyplot (vous vous souvenez des graphiques sur Pix ?).

Enfin , on crée des listes vides où pour chaque tri, on stockera les durées d'exécution des programmes.

import random
from time import *
import matplotlib.pyplot as plt
n=[100,1000,5000,8000,10000]
duree_insertion=[]
duree_selection=[]
duree_sort=[]
duree_sorted=[]

Ensuite, une fois qu'on en a fini avec les préparatoires, on va écrire une fonction qui génère une liste de valeurs aléatoires entre 0 et 100 et dont la longueur dépend de la liste n, définie plus tôt.

def creation_liste_aleatoire(n):

liste = []

for k in range(n): liste.append(random.randint(0,100)) return liste

Voila maintenant la partie la plus difficile et longue, on va définir la fonction de tri de la liste et sa mesure de temps d'exécution.

Voici comment on va procéder pour chaque tri:

- Grace à la fonction * de time, on va définir un temps T1, qui sera mesuré avant l'exécution du programme de tri.

-On crée le programme de tri (détail dans les 4 boutons plus haut).

-On mesure un autre temps T2, qui sera mesuré après le tri complet de la liste, on lui soustrait T1 et on a notre temps d'exécution.

-On met ce temps dans la liste (définie au début) correspondant au tri en question.

Bon...là encore, c'est facile: D'abord, on définit T1, puis on exécute le tri rapide sort et après, on définit T2, on lui soustrait T1 et on met le résultat dans "duree_sort".

Une fois que c'est fait, on mélange à nouveau la liste pour le tri suivant.

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)

ça , c'est optionnel, si vous voulez à chaque étape du projet, vérifier que le calcul se fait bien.

Pareil, ici on fait la même chose, sauf que là on met le tri "sorted" à la place de "sort"

Même chose, sauf que vous avez vu? Oui! On doit mettre l'algorithme de tri par insertion en entier dans la fonction au lieu de mettre juste une fonction comme pour "sort" et "sorted".

Comme pour le tri par insertion, sauf qu'on ne met pas le même algorithme de tri.

PFFfffiou! Quel gros morceau c'était ce bout de code! Maintenant il ne reste plus qu'à définir la fonction qui permet de tracer un graphique pour le résultat. Tiens tiens... ça vous rappelle pas quelque chose? Si ! Le projet Pix, si vous l'avez pas vu ou que vous voulez savoir comment ça marche, cliquez ici >>>>>>>>>>>>>>>>>

Virus.exe (hehehe)

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='green', label = 'sort', marker="+")

plt.plot(n,duree_sorted,"o", color='blue', 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ée')

plt.title("Durée versus nombre d'éléments à trier ")

plt.legend()

plt.grid(True)

plt.show()tracer_figure(duree_sort,duree_sorted,duree_insertion, duree_selection,n)

Maintenant si vous exécutez le script, vous devriez avoir un truc à peu près comme ça:

(mauvais script :( )

Traceback (most recent call last):
File "<interactive input>", line 1, in <module>
File "U:\NSI\tris\auto_et_tra_mesdur_tri_selec_ins_so_sor.py", line 149, in tracer_figure
plt.plot(n,duree_fusion_recursive,"o",color='pink',label='fusion',marker='3')
File "C:\EduPython\App\lib\site-packages\matplotlib\pyplot.py", line 2796, in plot
is not None else {}), **kwargs)
File "C:\EduPython\App\lib\site-packages\matplotlib\axes\_axes.py", line 1665, in plot
lines = [*self._get_lines(*args, data=data, **kwargs)]
File "C:\EduPython\App\lib\site-packages\matplotlib\axes\_base.py", line 225, in __call__
yield from self._plot_args(this, kwargs)
File "C:\EduPython\App\lib\site-packages\matplotlib\axes\_base.py", line 391, in _plot_args
x, y = self._xy_from_xy(x, y)
File "C:\EduPython\App\lib\site-packages\matplotlib\axes\_base.py", line 270, in _xy_from_xy
"have shapes {} and {}".format(x.shape, y.shape))
ValueError: x and y must have same first dimension, but have shapes (11,) and (21789,)

Bon ... Comme vous avez vu, ça marche pas :(

Mais analysons: Le script nous dit que dans le tri par fusion, il n'y a aucune valeur et par conséquent le graphique ne s'affiche pas.

Mais oui! J'ai oublié de mettre la fonction de tri par fusion!!!!!!!!

Et ça marche Paaaaaaaaaaaaaas...

Voila, notre script est complet, maintenant, je vais devoir rajouter moi même des nouveaux tris au programme:

-Tri à bulle

-Tri par fusion

-Tri par fusion récursive

C'est plus dur...

Ma première étape à été d'aller chercher des codes sur internet, j'ai d'abord commen cé par le tri à bulle et je suis tombé sur ce site:[RIEN] qui contenait différents types de code à copier,

LE TRI A BULLES

ça:

Et j'ai trouvé ça:

Voir comment ces tris fonctionnent

def duree_tri_bulles(liste):
t1=time()
for i in range(len(liste),0,-1):
for j in range(0,i-1):
if liste[j+1]<liste[j]:
liste[j+1],liste[j]=liste[j], liste[j+1]
t2=time()
duree=t2-t1
#print("Tri à bulles, durée = " ,duree)
duree_bulles.append(duree)
random.shuffle(liste)

ça:

Et j'ai trouvé ça:

Mais j'ai pas trouvé le tri par fusion, tant pis je le met pas.

Maintenant, voici le code avec les tri ajoutés:

LE TRI PAR FUSION RéCURSIVE

import random from time import * import matplotlib.pyplot as plt n=[100,200,400,500,800,1000,1200,1400,1500,1800,2000,] #2100,2200,2400,2500,2800,3000,3100,3200,3400,3500,3800,4000,4100,4200,4400,4500,4800,5000 duree_insertion=[] duree_selection=[] duree_sort=[] duree_sorted=[] duree_bulles=[] duree_fusion=[] duree_fusion_recursive=[] liste2=[] 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) def duree_tri_bulles(liste): t1=time() for i in range(len(liste),0,-1): for j in range(0,i-1): if liste[j+1]

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)

def duree_tri_fusion(liste,liste2):
t1=time()

t2=time()
duree=t2-t1
#print("Tri par fusion, durée = " ,duree)
duree_fusion.append(duree)
random.shuffle(liste)

def duree_tri_fusion_recursive(liste):
t1=time()
tab=(liste)
if len(liste)>1:
mid = len(tab)//2
G = liste[:mid]
D = liste[mid:]
duree_tri_fusion_recursive(G)
duree_tri_fusion_recursive(D)
i = j = k = 0
while i < len(G) and j < len(D):
if G[i] < D[j]:
liste[k] = G[i]
i += 1
else:
liste[k] = D[j]
j += 1
k += 1
while i < len(G):
liste[k] = G[i]
i += 1
k += 1
while j < len(D):
liste[k] = D[j]
j += 1
k += 1

'''A = [64, 25, 12, 22, 11]
triFusion(A)'''
t2=time()
duree=t2-t1
#print("Tri par fusion récursive, durée = " ,duree)
duree_fusion_recursive.append(duree)
random.shuffle(liste)

for element in n:
liste= creation_liste_aleatoire(element)
print(element,"éléments fait. attente de la suite...")
duree_tri_insertion(liste)
duree_tri_selection(liste)
duree_tri_sort(liste)
duree_tri_sorted(liste)
duree_tri_bulles(liste)
duree_tri_fusion(liste,liste2)
duree_tri_fusion_recursive(liste)

def tracer_figure(duree_sort,duree_sorted,duree_insertion, duree_selection,duree_bulles,duree_fusion,duree_fusion_recursive,n):
plt.figure(figsize = (16, 10))
plt.plot(n,duree_sort,"o", color='green', label = 'sort', marker="+")
plt.plot(n,duree_sorted,"o", color='blue', label= 'sorted', marker="x")
plt.plot(n,duree_insertion,"o", color='red', label= 'insertion', marker="1")
plt.plot(n,duree_selection,"o", color='black', label= 'selection', marker="2")
plt.plot(n,duree_bulles,"o",color='orange',label='fusion',marker='4')
plt.plot(n,duree_fusion,"o",color='yellow',label='fusion',marker='+')
plt.plot(n,duree_fusion_recursive,"o",color='pink',label='fusion',marker='3')
plt.xlabel('n')
plt.ylabel('Durée')
plt.title("Durée versus nombre d'éléments à trier ")
plt.legend()
plt.grid(True)
plt.show()
tracer_figure (duree_sort,duree_sorted,duree_insertion, duree_selection,duree_bulles,duree_fusion,duree_fusion_recursive,n)

Le seul problème, c'est que je me coltine encore ce message d'erreur là:

Et grâce à un peu d'aide, je crois avoir trouvé ce qui ne va pas: Dans l'algorithme du tri par fusion récursive, j'ai tout réuni en une fonction, alors que NON NON NON NON ! Il faut séparer dans ce cas spécial la fonction de tri du code et la fonction de mesure de la durée car si vous avez regardé le code , vous avez vu que dans l'algorithme de tri, il se réexécute lui même, ce qui fait qu'on a exécutions sur exécutions ce qui fait qu'on a beaucoup plus de x que de y dans le graphique. Problème résolu.

Voici la fonction corrigée:

def tri_fusion_recursive(liste):
tab=(liste)
if len(liste)>1:
mid = len(tab)//2
G = liste[:mid]
D = liste[mid:]
tri_fusion_recursive(G)
tri_fusion_recursive(D)
i = j = k = 0
while i < len(G) and j < len(D):
if G[i] < D[j]:
liste[k] = G[i]
i += 1
else:
liste[k] = D[j]
j += 1
k += 1
while i < len(G):
liste[k] = G[i]
i += 1
k += 1
while j < len(D):
liste[k] = D[j]
j += 1
k += 1

'''A = [64, 25, 12, 22, 11]
triFusion(A)'''

def duree_tri_fusion_recursive(liste):
t1=time()

t2=time()
duree=t2-t1
#print("Tri par fusion récursive, durée = " ,duree)
duree_fusion_recursive.append(duree)
random.shuffle(liste)

Maintenant si vous exécutez le script, vous devriez avoir un truc à peu près comme ça:

Et Voilà!

Revenir en haut de la page

novembre

Attention! Vu que je m'y suis pris tard sur ce projet, je ne citerait pas les problèmes et bugs rencontés.

Mais c'est kwa le tri par:

Bouh

import random from time import * import matplotlib.pyplot as plt n=[100,1000,5000,8000,10000] duree_insertion=[] duree_selection=[] duree_sort=[] duree_sorted=[]

LE TRI A BULLES

ça:

Et j'ai trouvé ça:

ça:

Et j'ai trouvé ça:

Mais j'ai pas trouvé le tri par fusion, tant pis je le met pas.

Mais j'ai pas trouvé le tri par fusion, tant pis je le met pas.

LE TRI PAR FUSION RéCURSIVE

Et Voilà!

import random
from time import *
import matplotlib.pyplot as plt
n=[100,1000,5000,8000,10000]
duree_insertion=[]
duree_selection=[]
duree_sort=[]
duree_sorted=[]