Pour le projet n°2 nous voulons étudier automatiquement les durées d'exécutions d'un algorithme de trie pour un dizaine de listes aléatoire de taille différentes par python. Nous avons essayer avec plusieurs tris possible comme:

-tri sort

-tri sorted

-tri bulle

-tri sélection

-tri insertion

Voici le programme:

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_bulle=[]
resultats_selection=[]
resultats_insertion=[]
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)

def duree_tri_sorted (liste):
  t1=time()
  liste_triee=sorted(liste)
  t2=time()
  duree=t2-t1
  resultats_sorted.append(duree)
  random.shuffle(liste)

def duree_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
  resultats_bulle.append(duree)
  random.shuffle

def tri_selection(tab):
  for i in range(len(tab)):
       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_selection.append(duree)
  random.shuffle(liste)

def tri_insertion(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_insertion.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_bulle(L)
  duree_tri_selection(L)
  duree_tri_insertion(L)
print(resultats_sort)
print(resultats_sorted)
print(resultats_bulle)
print(resultats_selection)
print(resultats_insertion)

def modele(liste):
  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,listebulle,listeselection,listeinsertion,nliste):
  plt.figure(figsize = (16, 10))
  plt.plot(nliste,listesort,'o',label='sort',color='red',marker="+")
  plt.plot(nliste,listesorted,'o',label='sorted',color='blue',marker="x")
  plt.plot(nliste,listebulle,'o',label='bulle',color='green',marker="2")
  plt.plot(nliste,listeselection,'o',label='selection',color='black',marker="1")
  plt.plot(nliste,listeinsertion,'o',label='insertion',color='purple',marker="2")
  plt.xlabel('n')
  plt.ylabel('Durée')
  plt.title("Durée versus n")
  plt.legend()

  model()

  model()

  model()

  model()

  model()
  plt.grid(True)
  plt.show()

tracer_figure(resultats_sort,resultats_sorted,resultats_bulle,resultats_selection,resultats_insertion,n_liste)