NSI - Loïs
Tris et vitesses de tri :
Programme de départ :
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
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
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)
Le programme ci-dessus permet de comparer le temps que mettent différentes fonctions de tri pour trier une liste générée aléatoirement à l'aide de la bibliothèque random dont la longueur va de 100 à 10 000 éléments grâce à la bibliothèque time et qui ensuite trace un graphique des temps grâce à la bibliothèque matplotlib. L'idée ici est de compléter ce programme afin qu'il compare plus d'algorithmes de tri. Pour cela j'effectue des recherches sur internet pour trouver les algorithmes de tri déjà prêts et pour les insérer plus rapidement dans le programme.
Programme de tri à bulle trouvé sur internet (GIThub) :
def bubble_sort(arr):
for i in range(len(arr) - 1, 0, -1):
for j in range(i):
if arr[j] > arr[j + 1]:
arr[j + 1], arr[j] = arr[j], arr[j + 1]
return arr
Programme modifié :
def tri_bulle(liste):
t1=time()
for i in range(len(liste) - 1, 0, -1):
for j in range(i):
if liste[j] > liste[j + 1]:
liste[j + 1], liste[j] = liste[j], liste[j + 1]
t2=time()
duree=t2-t1
duree_bulle.append(duree)
random.shuffle(liste)
Programme de tri rapide trouvé sur internet(encore GIThub) :
def quick_sort(arr):
if len(arr) < 2:
return arr
pivot_index = len(arr) - 1
pivot = arr[pivot_index]
lesser = [item for item in arr[:pivot_index] if item <= pivot]
greater = [item for item in arr[:pivot_index] if item > pivot]
return quick_sort(lesser) + [pivot] + quick_sort(greater)
Programme modifié :
def quick_sort(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
dureee_rapide.append(duree)
liste.shuffle
à ce stade, aucune erreur n'a été rencontrée, les programmes trouvés sur GIThub fonctionnent bien et je n'ai pas fait d'erreur en les modifiant, cependant je m'apprête maintenant à ajouter un nouvel algorithme de tri qui sera source de nombreuses erreurs :
Le tri par fusion récursif
On dit d'une fonction qu'elle est récursive lorsqu'elle s'appelle elle même pendant son exécution, c'est le cas dans le code ci-dessous avec la fonction msort qui s'appelle elle même.
Programme trouvé sur internet (GIThub) :
def m(left, right):
if not len(left) or not len(right):
return left or right
result = []
i, j = 0, 0
while len(result) < len(left) + len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
if i == len(left) or j == len(right):
result.extend(left[i:] or right[j:])
break
return result
def msort(list):
if len(list) < 2:
return list
middle = int(len(list) / 2)
left = msort(list[:middle])
right = msort(list[middle:])
return m(left, right)
lst = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(lst)
print("\n")
print("Sorted List:")
print(msort(lst))
Programme modifié (1) :
def m(left, right):
if not len(left) or not len(right):
return left or right
result = []
i, j = 0, 0
while len(result) < len(left) + len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
if i == len(left) or j == len(right):
result.extend(left[i:] or right[j:])
break
return result
def tri_recursif(list):
t1=time()
if len(list) < 2:
return list
middle = int(len(list) / 2)
left = tri_recursif(list[:middle])
right = tri_recursif(list[middle:])
t2=time()
duree_recursif= t2-t1
duree_recursif.append(duree)
random.shuffle(liste)
return m(left, right)
Je modifie le programme comme j'ai fait pour les autres et....
Traceback (most recent call last):
File "U:\prive\NSI programmes\bidule en cours.py", line 141, in <module>
tri_recursif(liste)
File "U:\prive\NSI programmes\bidule en cours.py", line 47, in tri_recursif
left = tri_recursif(list[:middle])
File "U:\prive\NSI programmes\bidule en cours.py", line 47, in tri_recursif
left = tri_recursif(list[:middle])
File "U:\prive\NSI programmes\bidule en cours.py", line 47, in tri_recursif
left = tri_recursif(list[:middle])
[Previous line repeated 2 more times]
File "U:\prive\NSI programmes\bidule en cours.py", line 48, in tri_recursif
right = tri_recursif(list[middle:])
File "U:\prive\NSI programmes\bidule en cours.py", line 51, in tri_recursif
duree_recursif.append(duree)
AttributeError: 'float' object has no attribute 'append'
Toutes ces lignes d'erreur pour dire que je me suis embrouillé dans le nom des variables et de la méthode append...
Programme modifié (2) :
(J'ai souligné les lignes où je me suis lamentablement trompé)
def tri_recursif(list):
t1=time()
if len(list) < 2:
return list
middle = int(len(list) / 2)
left = tri_recursif(list[:middle])
right = tri_recursif(list[middle:])
t2=time()
duree = t2-t1
duree_recursif.append(duree)
random.shuffle(liste)
return m(left, right)
C'est sensé fonctionner maintenant... non ?
Traceback (most recent call last):
File "U:\prive\NSI programmes\bidule en cours.py", line 157, in <module>
tracer_figure (duree_sort,duree_sorted,duree_insertion, duree_selection,duree_bulle,duree_rapide,duree_recursif,n)
File "U:\prive\NSI programmes\bidule en cours.py", line 150, in tracer_figure
plt.plot(n,duree_recursif,"o",color="purple",label = "récursif",marker = "x")
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 (3,) and (6097,)
J'ai mis énormément de temps à comprendre mon erreur jusqu'au moment où j'ai eu l'idée de regarder le nombre de valeurs dans la liste qui contient toutes les durés mesurées pour le tri récursif, et là j'ai de suite compris le problème :
>>>duree_recursif
[0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0010039806365966797,
0.0010039806365966797,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0009968280792236328,
0.0009968280792236328,
0.0020008087158203125,
0.0,
0.0,
0.0,
0.00099945068359375,
0.00099945068359375,
0.0,
0.0,
0.0,
0.0,
0.0,
0.00099945068359375,
0.0,
0.0010001659393310547,
0.0,
0.0,
0.0010001659393310547,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0010001659393310547,
0.0030052661895751953,
0.005006074905395508,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0010416507720947266,
0.0010416507720947266,
0.0011997222900390625,
0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
Cela ne représente même pas1/100 des valeurs que j'ai dans la liste, rappelons qu'elle est sensé en contenir 4 avec le programme actuel...
MAIS
Notre cher professeur nous a présenté une idée que je suis obligé de qualifier de brillante : créer une troisième fonction qui elle ne sert qu'à mesurer le temps que prend l'algorithme à trier
Voilà donc le tri par fusion récursif 2.2 :
def m(left, right): ...
def tri_recursif(list):
if len(list) < 2:
return list
middle = int(len(list) / 2)
left = tri_recursif(list[:middle])
right = tri_recursif(list[middle:])
random.shuffle(liste)
return m(left, right)
def duree_tri_par_fusion_recursif (L):
t1=time()
L=tri_recursif(L)
t2= time()
duree = t2-t1
duree_recursif.append(duree)
La fonction m n'a pas changé depuis le début, la deuxième fonction je lui ai simplement retiré les mesures de temps avant de les mettre dans la troisième fonction que j'ai moi même fièrement plagié sur le programme de Mr Laclaverie. C'est celle-ci que j'appelle pour tracer le tableau.
Il reste cependant un défaut à tout ça : le tri par fusion récursif est sensé être rapide or voila le tableau que j'obtiens :
La petite croix violette isolée en haut c'est celle du tri par fusion récursif. Elle est très haut au dessus des autres sachant qu'elle devrait être en bas avec les autres, mais ça aurait été trop simple si ça avait marché correctement au bout de 3 heures après tout.
def tri_recursif(list):
if len(list) < 2:
return list
middle = int(len(list) / 2)
left = tri_recursif(list[:middle])
right = tri_recursif(list[middle:])
random.shuffle(liste)
return m(left, right)
Je vous laisse un peu de temps pour trouver l'erreur lamentablement bête que j'ai fait....
def tri_recursif(list):
if len(list) < 2:
return list
middle = int(len(list) / 2)
left = tri_recursif(list[:middle])
right = tri_recursif(list[middle:])
return m(left, right)
random.shuffle(liste)
Si je dois décrire avec une image ce que faisaient ces lignes, je dirais que je donnais un jeu de cartes à trier à mon programme et dès qu'il s'apprêtait à réussir je le remélangeais aléatoirement, en inversant ainsi le return et le shuffle comme me l'a gentiment suggéré Jules on obtient un magnifique tableau :
