ELOÏSE NSI
Projet 4 : Durées des différents tris
Les différents tris utilisés
-
Étape 1 : Tri par insertion
Tout d'abord, nous avons corrigé un programme de tri par insertion contenant une erreur (en rouge) afin de pouvoir trier n'importe quelle liste avec la technique de l'insertion.
A=[3,2,3,24,321,11111111,5,6]
print("tableau non trié",A)
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
print("tableau trié",A)
-
Étape 2 : Tri par sélection
Nous avons ensuite fait de même avec un programme de tri par sélection mais il n'y avait pas d'erreur.
-
Étape 3 : Méthodes sort et sorted
A=[3,-2,3,24,321,11111111,5,6]
print("tableau non trié",A)
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
print("tableau trié",A)
Ensuite, nous avons vu la méthode sort qui permet de trier la liste sans créer de copie. Et la fonction sorted qui permet de créer une copie triée de liste.
liste=[11,28,6,57,32,985,42,7,12]
liste.sort()
liste2=sorted(liste)
L'élaboration du programme complet
-
Étape 4 : Création de listes aléatoires
Après cela, nous avons mis au point un programme permettant de créer des listes aléatoires, avec des nombres d'éléments allant de 100 à 10000. Nous avons donc utilisé la bibliothèque random avec random.randint().
import random
n=[100,1000,5000,8000,10000]
def creation_liste_aleatoire():
liste = [ ]
for k in n:
liste.append(random.randint(0,100))
return liste
-
Étape 5 : Création de fonctions
Nous avons ensuite créé plusieurs fonctions contenant chacune le programme d'une technique de tri, dans le but de pourvoir ensuite mesurer leurs durées d'exécution. Nous avons ajouté un random.shuffle à la fin de chaque fonction pour remélanger la liste après chaque tri.
-
Étape 6 : Mesure des durées
Pour mesurer les temps d'exécution de chacun des tris, nous avons utilisé la bibliothèque time. Nous avons donc ajouté à chacune des fonctions de tri une mesure de temps au début et à la fin de la fonction pour ensuite calculer la durée d'exécution en faisant la différence. Ces durées ont ensuite été ajoutées à des listes pour chaque tri. (ci-contre l'exemple avec sort)
import random
from time import *
n=[100,1000,5000,8000,10000]
duree_sort=[]
duree_sorted=[]
duree_insertion=[]
duree_selection=[]
def creation_liste(n):
liste=[]
for k in 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 par sort, durée = ",duree)
duree_sort.append(duree)
random.shuffle(liste)
-
Étape 7 : Exécution des fonctions
Enfin, nous avons finalement ajouté une boucle for à la fin du programme pour pouvoir exécuter les mesures de durées pour chaque nombre d'éléments dans la liste aléatoire.
for element in n:
print(element)
liste=creation_liste(n)
duree_tri_sort(liste)
duree_tri_sorted(liste)
duree_tri_insertion(liste)
duree_tri_selection(liste)
Affichage en graphique
-
Étape 8 : Tracé du graphique
Nous avons ensuite essayé de l'afficher sous forme de graphique pour plus de compréhension. Pour cela, nous nous sommes servi du programme déjà fait que nous avions utilisé dans le projet de notation pix. Nous avons dû modifier plusieurs éléments afin d'afficher plusieurs points, de différentes couleurs, avec différents marqueurs et différents labels.
def tracer_figure(n,duree_sort,duree_sorted,duree_insertion,duree_selection):
plt.figure(figsize=(16,10))
plt.plot(n,duree_sort,"o",color="yellow",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="green",label="séléction",marker="2")
plt.xlabel('Nombre éléments')
plt.ylabel('Durée')
plt.title("Durées des tris")
plt.legend()
plt.show()
tracer_figure(n,duree_sort,duree_sorted,duree_insertion,duree_selection)
Recherche de nouveaux tris
-
Étape 9 : Ajout du tri à bulle
Pour finir, nous avons cherché à comparer la vitesse d'exécution d'autres tris comme par exemple le tri à bulle, le tri rapide, le tri par fusion et le tri par fusion récursif. Nous avons donc cherché sur internet des codes de ces tris pour les adapter et les intégrer dans notre programme.
Pour ma part, j'ai donc trouvé un programme de tri à bulle que j'ai tenté d'adapter mais j'ai rencontré une difficulté : ma mesure de temps à la fin du programme ne s'exécutait pas car le return de la fonction se plaçait avant et donc ne prenait pas en compte les lignes de codes qui suivaient. Après modification de mon erreur, j'ai pu l'intégrer dans le programme.
-
Étape 10 : Ajout du tri rapide
J'ai également recherché un code de tri rapide que j'ai adapté afin de l'ajouter dans le programme. Je n'ai pas rencontré de difficultés particulières car il n'y avait pas de return, donc c'était plus simple. Je l'ai donc ajouté dans le programme et dans le tracé du graphique.
def duree_tri_bulle(liste):
t1=time()
k = len(liste)
# Traverser tous les éléments du tableau
for i in range(k):
for j in range(0, k-i-1):
# échanger si l'élément trouvé est plus grand que le suivant
if liste[j] > liste[j+1] :
liste[j], liste[j+1] = liste[j+1], liste[j]
t2=time()
duree=t2-t1
duree_bulle.append(duree)
random.shuffle(liste)
return liste
def duree_tri_rapide(L):
"""trirapide(L): tri rapide (quicksort) de la liste L"""
t1=time()
def trirap(L, g, d):
pivot = L[(g+d)//2]
i = g
j = d
while True:
while L[i]<pivot:
i+=1
while L[j]>pivot:
j-=1
if i>j:
break
if i<j:
L[i], L[j] = L[j], L[i]
i+=1
j-=1
if g<j:
trirap(L,g,j)
if i<d:
trirap(L,i,d)
g=0
d=len(L)-1
trirap(L,g,d)
t2=time()
duree=t2-t1
duree_rapide.append(duree)
random.shuffle(L)
-
Étape 11 : Ajout du tri par fusion récursif
Enfin, j'ai voulu ajouter le tri par fusion récursif dans mon programme. J'ai tout d'abord trouvé un code de tri par fusion récursif sur internet que j'ai testé et tenté d'adapter pour mon programme. Cependant, j'ai rencontré une nouvelle difficulté : le programme contenait deux fonctions qui n'étaient pas appelées dans la fonction principale.
Après avoir sollicité une nouvelle fois l'aide du professeur, il m'a donné un programme de tri par fusion récursif plus simple et qui fonctionnait. Je l'ai alors ajouté à mon programme principal et dans le tracé de la figure.
Mais j'ai rencontré un nouveau problème à ce moment-là : lors du tracé de la figure, les listes n et duree_fusion_recursif n'étaient pas de la même taille.
J'ai donc corrigé le code en créant une nouvelle fonction contenant seulement la mesure de durée et l'appel de la fonction de fusion récursif.
Pour modifier ce code, je l'ai isolé dans un programme qui n'exécutait que lui et je me suis assurée que la longueur de la liste duree_fusion_recursif était bien la même que n.
Enfin, j'ai reproduis les modifications dans le programme complet et j'ai pu tracer la figure complète.
def duree_tri_fusion(L):
t1=time()
def triFusion(L):
if len(L) == 1:
t2=time()
duree=t2-t1
duree_fusion.append(duree)
random.shuffle(liste)
print(duree_fusion_recursif)
return L
else:
return fusion( triFusion(L[:len(L)//2]) , triFusion(L[len(L)//2:]) )
def fusion(A,B):
if len(A) == 0:
return B
elif len(B) == 0:
return A
elif A[0] <= B[0]:
return [A[0]] + fusion( A[1:] , B )
else:
return [B[0]] + fusion( A , B[1:] )
def fusion(L1,L2):
n1 = len(L1)
n2 = len(L2)
L12 = [0]*(n1+n2)
i1 = 0
i2 = 0
i = 0
while i1<n1 and i2<n2:
if L1[i1] < L2[i2]:
L12[i] = L1[i1]
i1 += 1
else:
L12[i] = L2[i2]
i2 += 1
i += 1
if i1<n1:
while i1<n1:
L12[i] = L1[i1]
i1 += 1
i += 1
else:
while i2<n2:
L12[i] = L2[i2]
i2 += 1
i += 1
return L12
def tri_fusion_recursif(L):
t1=time()
m = len(L)
if m > 1:
p = int(m/2)
L1 = L[0:p]
L2 = L[p:m]
tri_fusion_recursif(L1)
tri_fusion_recursif(L2)
L[:] = fusion(L1,L2)
t2=time()
duree=t2-t1
duree_fusion_recursif.append(duree)
random.shuffle(liste)
Programme final
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_bulle=[]
duree_rapide=[]
duree_fusion_recursif=[]
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_bulle(liste):
t1=time()
k = len(liste)
# Traverser tous les éléments du tableau
for i in range(k):
for j in range(0, k-i-1):
# échanger si l'élément trouvé est plus grand que le suivant
if liste[j] > liste[j+1] :
liste[j], liste[j+1] = liste[j+1], liste[j]
t2=time()
duree=t2-t1
duree_bulle.append(duree)
random.shuffle(liste)
return liste
def duree_tri_rapide(L):
"""trirapide(L): tri rapide (quicksort) de la liste L"""
t1=time()
def trirap(L, g, d):
pivot = L[(g+d)//2]
i = g
j = d
while True:
while L[i]<pivot:
i+=1
while L[j]>pivot:
j-=1
if i>j:
break
if i<j:
L[i], L[j] = L[j], L[i]
i+=1
j-=1
if g<j:
trirap(L,g,j)
if i<d:
trirap(L,i,d)
g=0
d=len(L)-1
trirap(L,g,d)
t2=time()
duree=t2-t1
duree_rapide.append(duree)
random.shuffle(L)
def fusion(L1,L2):
n1 = len(L1)
n2 = len(L2)
L12 = [0]*(n1+n2)
i1 = 0
i2 = 0
i = 0
while i1<n1 and i2<n2:
if L1[i1] < L2[i2]:
L12[i] = L1[i1]
i1 += 1
else:
L12[i] = L2[i2]
i2 += 1
i += 1
if i1<n1:
while i1<n1:
L12[i] = L1[i1]
i1 += 1
i += 1
else:
while i2<n2:
L12[i] = L2[i2]
i2 += 1
i += 1
return L12
def tri_fusion_recursif(L):
n = len(L)
if n > 1:
p = int(n/2)
L1 = L[0:p]
L2 = L[p:n]
tri_fusion_recursif(L1)
tri_fusion_recursif(L2)
L[:] = fusion(L1,L2)
return L
def duree_tri_fusion_recursif(L):
t1=time()
tri_fusion_recursif(L)
t2=time()
duree=t2-t1
duree_fusion_recursif.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_bulle(liste)
duree_tri_rapide(liste)
duree_tri_fusion_recursif(liste)
def tracer_figure(n,duree_sort,duree_sorted,duree_insertion,duree_selection,duree_bulle,duree_rapide,duree_fusion_recursif):
plt.figure(figsize=(16,10))
plt.plot(n,duree_sort,"o",color="yellow",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="green",label="séléction",marker="2")
plt.plot(n,duree_bulle,"o",color="purple",label="bulle",marker="3")
plt.plot(n,duree_rapide,"o",color="orange",label="rapide",marker="4")
plt.plot(n,duree_fusion_recursif, "o",color="brown",label="fusion récursif",marker="+")
plt.xlabel('Nombre éléments')
plt.ylabel('Durée')
plt.title("Durées des tris")
plt.legend()
plt.show()
tracer_figure(n,duree_sort,duree_sorted,duree_insertion,duree_selection,duree_bulle,duree_rapide,duree_fusion_recursif)
