LOUDIER Sam
Les Tris
Dans ce tp, nous devons trouver des méthodes différentes pour trier une liste non triée d'un certain nombre d'élément
Le tri par insertion
Ce tri consiste, à chaque étape à rajouter un nouvel élément de la liste en l'insérant à sa place dans une sous liste préalablement trié.
En python, cela donne :
​
A=[3,2,3,24,321,11111111,5,6]
print("tableau non trié",A)
for j in range (1,len(A)):
key= A[j]
print("j=",j)
print("key",key)
i= j-1
print("i",i)
print("condition", "i=",i,i>0 and A[i]>key)
while i>= 0 and A[i]>key:
print("condition","i",i,i>0 and A[i]>key)
A[i+1]=A[i]
print("A[i+j]",A[i+1])
i=i-1
print("A[i+1]",A[i+1])
A[i+1]=key
print("A[i+1]",A[i+1])
print("condition","i=",i,i>0 and A[i]>key)
print("tableau trié",A)
​
Console : ( si on enlève tout les prints sauf le dernier)
tableau trié [2, 3, 3, 5, 6, 24, 321, 11111111]
Le Tri par sélection du minimum
Ce tri consiste à chercher le minimum de la liste et à le placer à la première position puis à chercher le minimum de la liste restante qu'on place en deuxième position etc...
En python, cela donne :
​
A=[6,9,-9,3,2,3,24,321,11111111,5,6]
print("tableau non trié",A)
for i in range(len(A)):
min = i
print("min=", min)
print("i =",i)
for j in range(i+1,len(A)):
print("j=",j)
if A[min]>A[j]:
print("condition", A[min]>A[j])
min=j
tmp=A[i]
print("tmp=",tmp)
A[i]=A[min]
print("A[i]=",A[i])
A[min]=tmp
print("A[min]=", A[min])
print("tableau trié",A)
​
Console :
tableau trié [-9, 2, 3, 3, 5, 6, 6, 9, 24, 321, 11111111]
Tri avec sort et sorted
Avant ça on peut désormais créer une liste aléatoire du nombre d'élément que l'on souhaite. Exemple avec 100 éléments :
​
import random
liste = []
for k in range(10):
liste.append(random.randint(0,100))
Sort et sorted sont deux méthodes de tris très efficaces.
Sorted permet de créer une copie de la liste triée contrairement à la méthode sort.
En python, cela donne :
​
liste2=sorted(liste)
liste.sort()
Mesure des durées des tris
Ce programme permet de mesurer la durée d'exécution des algorithmes de tris sort, sorted, insertion et sélection. Et de faire un tracé de ces durées.
import random
from time import *
import matplotlib.pyplot as plt
n=[100,200,500,1000,2000,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_insertion,duree_selection,duree_sort,duree_sorted,n):
plt.figure(figsize = (16, 10))
plt.plot(n,duree_sort,"o",color="black",label='sort',marker="+")
plt.plot(n,duree_sorted,"o",color='green',label='sorted',marker="x")
plt.plot(n,duree_insertion,"o",color='blue',label='insertion',marker="1")
plt.plot(n,duree_selection,"o",color='red',label='sélection',marker="2")
plt.xlabel('nombre éléments')
plt.xticks(rotation = 60)
plt.ylabel('en secondes ')
plt.title("Vitesse de tri des différents algorithmes")
plt.legend()
plt.show()
tracer_figure(duree_insertion,duree_selection,duree_sort,duree_sorted,n)
Je vais ensuite chercher sur Internet d'autres algorithmes de tris que je pourrais ajouter à ce code.
J'ai ajouté le tri à bulles dont le programme est :
​
def duree_tri_bulles(liste):
t1=time()
for i in range(len(liste),0,-1):
for j in range(0,i-1):
if liste[j+1] < liste[j]:
liste[j+1] , liste[j] = liste[j] , liste[j+1]
t2=time()
duree=t2-t1
return liste
duree_bulles.append(duree)
random.shuffle(liste)
Mais après ça j'ai eu plusieurs erreurs car il faut rajouter au début du programme :
duree_bulles=[]
​
Ensuite pour tracer la figure il faut rajouter dans la définition du tracer et dans la fonction tracer figure:
duree_bulles
​
Et dans la boucle final aussi :
duree_bulles(liste)
​
Mais j'avais quand même un message d'erreur, et l'erreur venait de la définition du tri à bulle.
​
​
def duree_tri_bulles(liste):
t1=time()
for i in range(len(liste),0,-1):
for j in range(0,i-1):
if liste[j+1] < liste[j]:
liste[j+1] , liste[j] = liste[j] , liste[j+1]
t2=time()
duree=t2-t1
return liste
duree_bulles.append(duree)
random.shuffle(liste)
​
J'ai alors tentait des modifications,j'ai remarqué qu'il fallait échanger de place return liste et
duree_bulls.append(duree) et cela à fonctionner.
​
​
​
Le Tri naïf
def duree_tri_naif(liste):
t1=time()
R = []
while len(liste) > 0:
m = liste[0]
for i in range(1,len(liste)):
if liste[i] < m:
m = liste[i]
R += [ m ]
liste.pop( liste.index(m) )
t2=time()
duree=t2-t1
duree_naif.append(duree)
random.shuffle(liste)
return R
​
Après avoir ajouté ce code, j'ai ensuite fait les modifications nécessaires pour que cela fonctionne :
- ajout de duree_tri_naif(liste) dans la boucle finale
- ajout de duree_naif dans la définition tracer_figure et dans l'appelle de fonction tracer_figure
​
​
Le Tri Partition
J'ai rajouté un programme de tri qui s'appelle le tri par partitionnement qui utilise un pivot, exactement le même principe que le tri rapide.
​
def duree_tri_partition(liste):
t1=time()
n = len(liste)
pivot=liste[n-1]
i = 0
j = 0
while j < n-1:
if liste[j] <= pivot:
liste[i],liste[j] = liste[j],liste[i]
i += 1
j += 1
liste[n-1],liste[i] = liste[i],liste[n-1]
t2=time()
duree=t2-t1
duree_partition.append(duree)
random.shuffle(liste)
​
​
Après avoir fait les modifications dans la fonction du tracer en ajoutant : duree_partition
Et en ajoutant une liste duree_partition=[]
Et rajouter duree_partition(liste) dans la boucle finale
​
Mais l'algorithme ne fonctionne pas dans le programme ayant tout les algorithmes. Pourtant il fonctionne bien quand il est tout seul.
L'erreur viendrait de la fonction pivot=liste[n-1]
​