Tri et Vitesse de Tri
Programme d'origine
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 (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='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)
Voici le programme d'origine auquel il m'a été demandé d'ajouter différents tris qui étaient à trouver sur internet. Le but de ce programme est de calculer le temps que mettent des types de tris à trier des listes de valeurs aléatoires (complexité ) pour au final en faire un graphique. On utilise ainsi les bibliothèques : random,
time et matplotlib.
Tris trouvés sur internet
def duree_tri_bulle(A):
n = len(A)
t1=time()
for i in range(n):
for j in range(0, n-i-1):
if A[j] > A[j+1] :
A[j], A[j+1] = A[j+1], A[j]
t2=time()
duree=t2-t1
duree_bulle.append(duree)
Le tri a bulle est le premier que j'ai récupéré ( après avoir galéré pendant 45min sur le tri à fusion qui n'a pas marché ). Il consiste à faire une liste de seulement des deux premiers éléments de la liste, de les trier, puis d'avancer d'une valeur avant de recommencer. Il a été trouvé sur https://waytolearnx.com/2019/04/tri-a-bulle-en-python.html?utm_content=cmp-true
Le tri rapide est le second tri que j'ai pris il consiste à placer un élément du tableau (appelé pivot) à sa place définitive,puis en plaçant de part et d'autre du pivot les valeurs plus petites et plus grandes pour pouvoir les trier. Il a été trouvé sur https://marcarea.com/weblog/2019/02/06/quelques-algorithmes-de-tri-en-python
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
while i1<n1:
L12[i] = L1[i1]
i1 += 1
i += 1
while i2<n2:
L12[i] = L2[i2]
i2 += 1
i += 1
return L12
​
Le tri par fusion et par fusion récursif sont en réalité assez similaires, c'est pourquoi je me permets de les mettre ensembles dans l'explication des tris trouvés. En premier lieu le tri par fusion récursif va diviser le tableau en s'appelant lui même d'où sa récursivité puis les éléments divisés sont fusionnés par la fonction fusion, tandis que le tri par fusiuon fait le même principe en appelant la fonction tri fusion récursif. Elle ne s'appelle pas elle même, ce qui lui enlève son caractère récursif.
def duree_tri_rapide(liste):
t1=time()
if len(liste) < 2:
return liste
pivot_index = len(liste) - 1
pivot = liste[pivot_index]
lesser = [item for item in liste[:pivot_index] if item <= pivot]
greater = [item for item in liste[:pivot_index] if item > pivot]
t2= time()
duree=t2-t1
duree_rapide.append(duree)
Définir une fonction fusion pour le tri par fusion qu'il soit récursif ou non est obligatoire pourqu'il fonctionne. Cette fonction a pour but de fusionner de nouveau les listes qui ont été divisionnées par le tri par fusion et fusion récursif.
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)
​def duree_tri_fusion(L):
t1=time()
M = list(L)
tri_fusion_recursif(M)
t2=time()
duree=t2-t1
duree_fusion.append(duree)
return M
Programme Final
import random
from time import *
import matplotlib.pyplot as plt
n=[100,1000,5000,8000,10000,20000,50000]
#Essai en baissant le nombre de valeurs ou les valeurs elles-mêmes pas d'effet
duree_insertion=[]
duree_selection=[]
duree_sort=[]
duree_sorted=[]
duree_bulle=[]
duree_fusion=[]
duree_fusion_recursif=[]
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 (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(A):
n = len(A)
t1=time()
for i in range(n):
for j in range(0, n-i-1):
if A[j] > A[j+1] :
A[j], A[j+1] = A[j+1], A[j]
t2=time()
duree=t2-t1
duree_bulle.append(duree)
def duree_tri_rapide(liste):
t1=time()
if len(liste) < 2:
return liste
pivot_index = len(liste) - 1
pivot = liste[pivot_index]
lesser = [item for item in liste[:pivot_index] if item <= pivot]
greater = [item for item in liste[:pivot_index] if item > pivot]
t2= time()
duree=t2-t1
duree_rapide.append(duree)
random.shuffle(liste)
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
while i1<n1:
L12[i] = L1[i1]
i1 += 1
i += 1
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
def duree_tri_fusion_recursif(L):
t1=time()
tri_fusion_recursif(L)
t2=time()
duree=t2-t1
duree_fusion_recursif.append(duree)
def duree_tri_fusion(L):
t1=time()
M = list(L)
tri_fusion_recursif(M)
t2=time()
duree=t2-t1
duree_fusion.append(duree)
return M
#code trouvé sur https://www.f-legrand.fr/scidoc/docmml/algorithmes/general/tri/tri.html
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_fusion(liste)
duree_tri_fusion_recursif(liste)
duree_tri_rapide(liste)
def tracer_figure(n,duree_fusion_recursif,duree_fusion,duree_tri_bulle,duree_tri_insertion,duree_tri_selection,duree_tri_sort,duree_tri_sorted,duree_tri_rapide):
plt.figure(figsize = (16, 10))
plt.plot(n,duree_sort,"o",color="green",label="sort",marker="x")
plt.plot(n,duree_sorted, "o",color="red",label="sorted",marker="x")
plt.plot(n,duree_insertion, "o",color="blue",label="insertion",marker="x")
plt.plot(n,duree_selection, "o",color="grey",label="selection",marker="x")
plt.plot(n,duree_bulle, "o",color="purple",label="bulle",marker="x")
plt.plot(n,duree_fusion, "o",color="black",label="fusion",marker="x")
plt.plot(n,duree_fusion_recursif, "o",color="orange",label="fusion récursif",marker="x")
plt.plot(n,duree_rapide, "o",color="cyan",label="rapide",marker="x")
plt.xlabel('Longueur de liste')
plt.xticks(rotation = 60)
plt.ylabel('Durée')
plt.title("Le graphique encore plus beau")
plt.legend()
plt.show()
if __name__=="__main__":
Voici le programme final après avoir assemblé tous les tris cependant ça n'a pas été simple tout d'abord il a fallu créer une fonction ayant pour but de créer une liste aléatoire via la bilbliothèque random. Elle est visible ici.
<-------------------------
Le tri a bulle ici présent ne pas m'a pas trop posé problème, il était de loin le plus simple ( et le plus lent aussi c'était un enfer dès qu'on prenait une liste de plus de 5000 éléments ). J'ai ainsi pu le coder dès la première séance comme un grand sans l'aide de personne ( ce qui ne va pas durer... ).
<--------------
C'est là que les problèmes commencent à apparaître... Le programme n'était en soit pas compliqué à implémenter car il ne demandait presque aucune modification. CEPENDANT c'est sans compter un problème de récursivité qui était inhérent à python. Autrement dit ça marchait pas dès lors que la liste faisait plus de 1000 éléments. Néanmoins avoir un programme qui marche à moitié m'énervait un peu donc le code que vous voyez là a été subtilisé à l'élève Guillerme.
<--------------------------------------------------------------
<-----------------------------
<-------------------------
C'était le moment de prendre ma revanche face aux deux tris par fusions. Et ça a été une assez grosse surprise en réalité le problème était plutôt simple quand on se rend compte que les deux tris dépendent d'une fonction fusion qu'on avait pas copié-collé en se disant " Ça sert à rien ça fusionne les éléments mais la fonction va déjà le faire". Il m'a fallu la dernière heure de projet pour les mettre dans le code mais ce n'était insurmontable bien que j'ai mis du temps à comprendre le fait qu'une appel l'autre et que celle-ci s'appelle ensuite.
Ces quelques lignes pour tracer le graphique m'ont posé plus de problème que certains programmes de tri. Non pas parce que c'était difficile à comprendre juste parce qu'après avoir attendu 2min pour bien que les tous les tris s'effectuent on me dise que mon "marker" n'existe pas. Finalement j'en ai eu marre et j'ai mis des "x" pour tous les marker.
<----------------------
.png)
Voici le résultat avec une longueur maximale et 20 éléments et un temps d'attente approximatif de 10min qui ont semblé en être 1000 fois plus. On peut ainsi observer les différentes complexités des programmes comme celles du tri à bulle et celui par sélection qui sont les trainards du groupe. Finalement ce projet m'a paru plus simple que celui sur pix, peut être parce que je commence à devenir plus à l'aise en code, ou juste que j'ai eu de la chance.