top of page
Projet 2: Tris Objectif: Obtenir une courbe de tris et de durée en fonction du temps.
Pour cela nous allons utiliser différent tri. Pour vous expliquer le programme sera décortiqué puis un y aura le programme en entier.
Le programme est le suivant:
Donc là nous importons les bibliothèques :
-time: avec from time import *
-random: import random
-matplotlib.pyplot as plt: import matplotlib.pyplot as plt
-numpy as np: import numpy as np
Puis nous créons des listes vides générées aléatoirement pour chaque tri :
-sort
-sorted
-tri par insertion
-tri par selection
-tri a bulle
-fusion
Ici on va créer une fonction "création de liste" qui vont faire que dans les listes on va ajouter i qui va prendre les valeurs jusqu'à 1000 puis une boucle va être créée nommée k qui va prendre les valeurs jusqu'à 1000 puis va être rajoutée dans la liste aléatoirement avec des valeur de 0 a 100.
Ensuite va se créer des fonctions pour tous les tris donc là c'est le tri sort qui prend en paramètre liste. Puis t1 est affecté à time puis on va trier la liste avec le tri sort, t2 est affecté à time puis on va calculer la durée du temps d'exécution du programme en faisant t1-t2 puis les résultats du tri sort seront ajoutés dans durée et enfin la liste va être mélangée.
Le tri sorted qui prend en paramètre liste. Puis t1 est affecté à time puis on va trier la liste avec le tri sort, t2 est affecté à time puis on va calculer la durée du temps d'exécution du programme en faisant t1-t2 puis les résultats du tri sorted seront ajoutés dans durée et enfin la liste va être mélangée.
Tri insertion, le principe est que l'on considère que le début de la liste est déjà trié et on insère l'élément suivant à sa place dans la liste. Il n'a pas besoin de toutes les données de la liste pour débuter le tri il peut donc être utilisé lorsque les données sont en cours d'acquisition.
Tri selection
Tri a bulle
Tri fusion
Le tri fusion qui prend en paramètre liste. puis t1 est affecté à time puis on va trier la liste avec le tri sort, t2 est affecté à time puis on va calculer la durée du temps d'exécution du programme en faisant t1-t2 puis les résultats du tri fusion seront ajoutés dans durée et enfin la liste va être mélangée.
Une boucle est i est créé qui va prendre les valeurs de 1 a 10 puis ont créé un raccourci pour dire que L est affecté à création de liste puis le programme appelle toutes les durées des tris 10 fois avec chaque durée prenant L en paramètre.
Une fonction modèle prenant liste en paramètre permet de créer des courbes en fonction des abscisses et des ordonnées avec la fonction numpy.
Enfin une fonction tracer figure qui prend toutes les listes des tris en paramètre. Puis les points de tous les résultats sont tracés avec en légende les noms des tris pour les reconnaitre et leurs couleurs associées à leur marker. Et enfin des modeles (courbes) vont être tracés.
Puis la fonction est appelé.
Donc là on voit le résultat c'est normal que les points ne soient pas dans la courbe car il faudrait plus de valeurs et c'est une courbe représentative avec la légende en haut à droite et le titre en haut au milieu.
Programme en entier.
from time import *
import random
import matplotlib.pyplot as plt
import numpy as np
# liste initiale générée aléatoirement :
resultats_sort=[]
resultats_sorted=[]
resultats_tri_insertion=[]
resultats_tri_selection=[]
resultats_tri_bulle=[]
resultats_fusion=[]
n_liste=[]
def creation_de_liste():
liste = []
n_liste.append(i*1000)
for k in range(i*1000):
liste.append(random.randint(0,100))
return liste
# tri par la fonction sort()
def duree_tri_sort(liste):
t1=time()
#print(t1)
liste.sort()
t2=time()
#print(t2)
duree=t2-t1
resultats_sort.append(duree)
#print("durée du tri ",duree
random.shuffle(liste)
def duree_tri_sorted (liste):
t1=time()
liste_triee=sorted(liste)
t2=time()
duree=t2-t1
resultats_sorted.append(duree)
random.shuffle(liste)
# Programme Python pour l'implémentation du tri par insertion
def tri_insertion(tab):
# Parcour de 1 à la taille du tab
for i in range(1, len(tab)):
k = tab[i]
j = i-1
while j >= 0 and k < tab[j] :
tab[j + 1] = tab[j]
j -= 1
tab[j + 1] = k
def duree_tri_insertion (liste):
t1=time()
tri_insertion(liste)
t2=time()
duree=t2-t1
resultats_tri_insertion.append(duree)
random.shuffle(liste)
def tri_selection(tab):
for i in range(len(tab)):
# Trouver le min
min = i
for j in range(i+1, len(tab)):
if tab[min] > tab[j]:
min = j
tmp = tab[i]
tab[i] = tab[min]
tab[min] = tmp
return tab
def duree_tri_selection (liste):
t1=time()
tri_selection(liste)
t2=time()
duree=t2-t1
resultats_tri_selection.append(duree)
random.shuffle(liste)
def tri_bulle(tab):
n = len(tab)
# Traverser tous les éléments du tableau
for i in range(n):
for j in range(0, n-i-1):
# échanger si l'élément trouvé est plus grand que le suivant
if tab[j] > tab[j+1] :
tab[j], tab[j+1] = tab[j+1], tab[j]
def duree_tri_bulle(liste):
t1=time()
tri_bulle(liste)
t2=time()
duree=t2-t1
resultats_tri_bulle.append(duree)
random.shuffle(liste)
def fusion(L1,L2):
n1 = len(L1)
n2 = len(L2)
L12 = [0]*(n1+n2)
j1 = 0
j2 = 0
j = 0
while j1<n1 and j2<n2:
if L1[j1] < L2[j2]:
L12[j] = L1[j1]
j1 += 1
else:
L12[j] = L2[j2]
j2 += 1
j += 1
while j1<n1:
L12[j] = L1[j1]
j1 += 1
j += 1
while j2<n2:
L12[j] = L2[j2]
j2 += 1
j += 1
return L12
def duree_tri_fusion(liste):
t1=time()
fusion(L,L)
t2=time()
duree=t2-t1
resultats_fusion.append(duree)
random.shuffle(liste)
for i in range(1,11):
print(i)
L= creation_de_liste()
duree_tri_sort(L)
duree_tri_sorted(L)
duree_tri_insertion(L)
duree_tri_selection(L)
duree_tri_bulle(L)
duree_tri_fusion(L)
#print(resultats_sort)
#print(resultats_sorted)
#print(resultats_tri_insertion)
#print(resultats_tri_selection)
#print(resultats_tri_bulle)
#print(resultats_tri_fusion)
def modele(liste):
# Données expérimentales
x = np.array([i for i in range (1000,11000,1000)]) # valeurs en abscisse
y = np.array(liste) # valeurs en ordonnées
# Modelisation fonction linéaire
modele=np.polyfit(x,y,2)
xm = np.linspace(1000,11000,1000)
ym = modele[0]*xm*xm + modele[1]*xm +modele[2]
plt.plot(xm, ym, label="modèle y="+str(round(modele[0],9))+" xm*xm + "+str(round(modele[1],9))+"x")
def tracer_figure(listesort,listesorted, listeinsertion, listeselection, listebulle, listefusion, nliste):
plt.figure(figsize = (16, 10))
plt.plot(n_liste,resultats_sort,'o',label='sort', color= "red", marker="+")
plt.plot(n_liste,resultats_sorted,'o',label='sorted', color= "green", marker="x")
plt.plot(n_liste,resultats_tri_insertion,'o',label='insertion', color= "blue", marker="+")
plt.plot(n_liste,resultats_tri_selection,'o',label='selection', color= "purple", marker="+")
plt.plot(n_liste,resultats_tri_bulle,'o',label='bulle', color= "black", marker="x")
plt.plot(n_liste,resultats_fusion,'o',label='fusion', color= "brown", marker="x")
plt.xlabel('n')
plt.ylabel('Durée')
plt.title("Durée versus n ")
plt.legend()
modele(listesort)
modele(listesorted)
modele(listeinsertion)
modele(listeselection)
modele(listebulle)
modele(listefusion)
plt.grid(True)
plt.show()
tracer_figure(resultats_sort,resultats_sorted, resultats_tri_insertion, resultats_tri_selection, resultats_tri_bulle, resultats_fusion, n_liste)
bottom of page