Nous avons créer un programme permettant avec une liste aléatoire de calculer la durée pour trier la liste en question avec plusieurs techniques différentes ainsi que de tracer un graphique pour mieux comparer les durées des tris ensemble.

Les différents types de tris

Dans un même programme

Graphique correspondant au programme ci-contre

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)

Étape 1

Avec plusieurs recherches internets, j'ai cherché d'autres types de tri et son algorithme en Python dont le tri à bulle, le tri par fusion et le tri par fusion récursive. Je les intégrerai dans mon programme plus tard.

° Sur le site suivant, j'ai trouvé des informations intéressantes sur le tri à bulles en Python mais aussi en JavaScript, pour ceux que ça intéresse. Le voici : https://librecours.net/module/js/js04/tri.xhtml

J'ai réussi après quelques oublis par-ci par-là à obtenir une fonction pour mon tri à bulles qui marche et qui s'affiche correctement dans mon graphique.

Étape 2

Après le tri à bulles, j'ai décider de faire le même travail mais avec le tri par fusion. J'ai trouvé un site qui explique bien et nous fourni un petit algorithme pour Python. Voici le site en question :

https://www.f-legrand.fr/scidoc/docmml/algorithmes/general/tri/tri.html

J'ai changé et ajouté le nom de fonction pour qu'il soit plus représentatif, les t1 et t2 obligatoires, et les dernières instructions importantes comme "random.shuffle" et ".append" ; de plus j'ai ajouté la liste correspondante et la ligne pour insérer les résultats dans le graphique.

Plus précisément j'ai trouvé ça :

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

Ma fonction après tous les changements:

def duree_tri_fusion(L1,L2):
t1=time()
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
t2=time()
duree= t2-t1
print("Tri par fusion, durée =", duree)
duree_fusion.append(duree)
random.shuffle(liste)

Après avoir fait tout ça, j'ai obtenue une erreur :
Traceback (most recent call last):
File "U:\NSI\Chapitre tri\automatisation_et_trace_mesure_duree_tri_selection_insertion_sort_sorted.py", line 124, in <module>
duree_tri_fusion(liste)
TypeError: duree_tri_fusion() missing 1 required positional argument: 'L2'

-> Cela signifie qu'à la ligne 124, il manque une liste.

Bout de programme correspondant à l'erreur:

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_bulles(liste)
duree_tri_fusion(liste) corrigé -> duree_tri_fusion(liste,liste)

Étape 3

Après l'avoir corriger et vu que ça marchait, je suis tombé sur une nouvelle erreur que je n'ai pas compris au début. La voici :

Après avoir relu mon programme, j'ai remarqué que j'avais oublié de rajouter les deux fonctions trouvées dans ma fonction tracer_figure()

Je relance tout, j'attends que ça termine car c'est plus que long et mon espoir que ça marche est littéralement mort.

J'ai eu ça :

Traceback (most recent call last):
File "U:\NSI\Chapitre tri\automatisation_et_trace_mesure_duree_tri_selection_insertion_sort_sorted.py", line 141, in <module>
tracer_figure(duree_sort, duree_sorted, duree_insertion, duree_selection, duree_bulles, duree_fusion, n)
File "U:\NSI\Chapitre tri\automatisation_et_trace_mesure_duree_tri_selection_insertion_sort_sorted.py", line 133, in tracer_figure
plt.plot(n,duree_fusion, "o", color='brown', label= 'fusion', marker="4")
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 (5,) and (2, 0)

Comment dire que j'ai pas compris et que ça m'a un peu effrayée ?

Pour vérifier que le problème venait bien de la fonction duree_tri_fusion(), je l'ai mis en commentaire. Cela venait bien de là.

Avec l'aide de mon professeur, j'ai remarqué que ma fonction était totalement fausse. Ma fonction était incomplète.

Mon professeur m'a dit de créer deux autres fonctions pour que ça marche: une qui fait un tri par fusion et une qui fait une fusion tout simplement.

Pour que ça marche

def tri_fusion(liste):
n = len(L)
if n > 1:
   p = int(n/2)
   L1 = L[0:p]
   L2 = L[p:n]
   tri_fusion(L1)
   tri_fusion(L2)
   L[:] = fusion(L1,L2)

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 duree_tri_fusion(liste):
t1=time()
tri_fusion(liste)
t2=time()
duree= t2-t1
#print("Tri par fusion, durée =", duree)
duree_fusion.append(duree)
random.shuffle(liste)

(Oui, je sais. Mes erreurs sont la plupart du temps dû à des oublis bêtes)