TP sur les tris.
Le but de ce TP est de comparer la vitesse des différents types de tri qui existent.
Le plan pour créer ce programme est simple:
​
- Tout d'abord, on va importer certaines libraires pour réaliser des calculs et donner des résultats aléatoires.
- De plus, on va définir au préalable des listes contenant le temps de chaque tri.
- Après, on va écrire une fonction pouvant créer une liste aléatoire à partir d'un nombre donné d'éléments noté n.
- Ensuite, on recopiera les différents types de tri en ajoutant une variable t1 et t2 mesurant le temps du tri avec la librairie time et on fera en sorte de trier à nouveau la liste pour éviter de fausser nos mesure de tri.
- Une fois cela fait, on écrira une boucle permettant d'exécuter nos tris avec plusieurs éléments dans une liste au fur et à mesure
- Enfin, le programme évoluera dans deux cas :
-1er cas : on créera une fonction qui nous affichera un graphique nous montrant les courbes d'évolution du temps de ces tris au fur et à mesure des éléments d'une liste
-2ème cas : on calculera la moyenne de temps de ces tris car ceux ci peuvent différés selon la composition de la liste créée sur le hasard
!REMARQUE!
On pourrait très bien réunir les 2 cas en 1, donc afficher sur un graphique la moyenne du temps de chaque forme de tri. Seulement, les consignes n'allaient pas dans ce sens. Il se peut que je traite ce cas plus tard .
Commençons par exporter nos librairies et définir nos variables principales:
import random
from time import *
import matplotlib
n =[100,1000,2500]
duree_tri_insertion_l =[]
duree_tri_selection_l =[]
duree_tri_sort_l= []
duree_tri_sorted_l = []
duree_des_tri = []
import random
from time import *
import matplotlib
n =[100,1000,2500]
duree_tri_insertion_l =[]
duree_tri_selection_l =[]
duree_tri_sort_l= []
duree_tri_sorted_l = []
duree_des_tri = []
def creation_random_list(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
return(duree)
print("Tri sort, durée = " ,duree)
random.shuffle(liste)
def duree_tri_sorted(liste):
t1=time()
liste2=sorted(liste)
t2=time()
duree=t2-t1
return(duree)
print("Tri sorted, durée = " ,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
return(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
return(duree)
random.shuffle(liste)
Nous allons maintenant ajouter nos différents tris en ajoutant t1, t2, leurs différence pour obtenir le temps total du tri et une ligne de random.shuffle pour réarranger la liste aléatoirement :
Cas 1 :
Ici, on va traiter le cas du temps moyen de chaque tri.
Pour commencer, on va donc écrire une fonction permettant de faire la moyenne des valeurs d'une liste .
Ensuite, on va ajouter une boucle pour laquelle on va effectuer le temps de chaque tri selon une quantité d'éléments dans une liste et placer le temps obtenu dans une liste dont on calculera la moyenne juste après. De plus, on répétera ces tris selon un nombre arbitraire, ici 5. En effet, M.Gerlero a jugé que répéter 5 fois le calcul de tri était suffisant pour obtenir une moyenne correcte.
def Moyenne(liste):
sum = 0
Z = 0
for i in liste:
sum = i + sum
Z = Z + 1
Moy = sum/Z
return(Moy)
def Moyenne(liste):
sum = 0
Z = 0
for i in liste:
sum = i + sum
Z = Z + 1
Moy = sum/Z
return(Moy)
for i in n:
for k in range(5):
liste =creation_random_list(i)
duree_tri_insertion_l.append(duree_tri_insertion(liste))
duree_tri_selection_l.append(duree_tri_selection(liste))
duree_tri_sort_l.append(duree_tri_sort(liste))
duree_tri_sorted_l.append(duree_tri_sorted(liste))
Il ne nous reste plus qu'à calculer la moyenne de nos listes contenant nos durées pour chaque tri, puis affecter ces valeurs à une variable qu'on affichera et le tour est joué .
def Moyenne(liste):
sum = 0
Z = 0
for i in liste:
sum = i + sum
Z = Z + 1
Moy = sum/Z
return(Moy)
for i in n:
for k in range(5):
liste =creation_random_list(i)
duree_tri_insertion_l.append(duree_tri_insertion(liste))
duree_tri_selection_l.append(duree_tri_selection(liste))
duree_tri_sort_l.append(duree_tri_sort(liste))
duree_tri_sorted_l.append(duree_tri_sorted(liste))
duree_tri_insertion_l = Moyenne(duree_tri_insertion_l)
duree_tri_selection_l = Moyenne(duree_tri_selection_l)
duree_tri_sorted_l = Moyenne(duree_tri_sorted_l)
duree_tri_sort_l = Moyenne(duree_tri_sort_l)
duree_des_tri = duree_tri_sort_l,duree_tri_sorted_l,duree_tri_selection_l,duree_tri_insertion_l
print(duree_des_tri)
Cas 2 :
Ici, on va traiter le cas où nous devons afficher un graphique représentant tous les différents temps de chaque tri.
Pour commencer, on va créer une boucle
qui va générer une liste aléatoire et on va calculer les différents temps de tri de
chaque forme de tri :
Puis, on va créer une fonction qui va nous permettre de tracer sur un graphique les temps de chaque type de tri :
for element in n:
liste= creation_liste_aleatoire(element)
duree_tri_insertion(liste)
duree_tri_selection(liste)
duree_tri_sort(liste)
duree_tri_sorted(liste)
for element in n:
liste= creation_liste_aleatoire(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)
Je tient a préciser qu'ici, les valeurs de listes vont jusqu'à 10000. De plus, nous avons des points car nous avons mis "o" dans nos paramètres pour avoir uniquement des points, mais nous pouvons aussi avoir seulement des courbes. Les graphiques nous montrent donc :
