programme de 4 tris et leurs tracés
Programme:
import random
from time import *
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)
import matplotlib.pyplot as plt
def tracer_figure(n,duree_insertion,duree_selection,duree_sort,duree_sorted):
plt.figure(figsize = (16, 10))
plt.plot(n, duree_insertion,"o", color='green', label = 'insertion', marker='*')
plt.plot(n, duree_selection,"o", color='red', label = 'selection', marker='*')
plt.plot(n, duree_sort,"o", color='blue', label = 'sort', marker='*')
plt.plot(n, duree_sorted,"o", color='yellow', label = 'sorted', marker='*')
plt.xlabel("nombres d'éléments")
plt.xticks(rotation = 60)
plt.ylabel('duree')
plt.title("La duree des tris")
plt.legend()
plt.show()
if __name__=="__main__":
tracer_figure(n,duree_insertion, duree_selection,duree_sort,duree_sorted)
Explications:
Tout d'abord on va importer la bibliothèque random ainsi que la bibliothèque time où " * " ne va prendre que la fonction time de cette bibliothèque. On affecte à n la liste contenant 5 valeurs. On créer 4 listes vides. On définie la fonction creation_de_liste_aleatoire qui prend toutes les valeurs de n. On créer une liste vide puis on créer une boucle for où k va prendre toutes les valeurs de la liste n. On va ajouter à la liste des valeurs aléatoire entre 0 et 100, puis on renvoie la liste.
On définie une fonction creation_liste_aleatoire qui va prendre toutes les valeurs de la liste n. On affecte à la liste liste une liste vide. On créé une boucle où k prend toutes les valeurs de la liste n. On ajoute à la liste les valeurs aléatoires entre 0 et 100. Enfin on renvoie la liste.
On définie une fonction duree_tri_sort qui va prendre les valeurs de la liste. On affecte à T1 la valeur du temps à ce moment puis on appelle la fonction sort qui prend les valeurs de la liste liste (cette fonction va trier la liste automatiquement). On affecte à T2 la valeur du temps à ce moment puis on affecte à la variable duree t2-t1 et on ajoute cette dernière à la liste duree_sort le #print est en commentaire car c'était pour vérifier que cela marchait. Enfin on mélange la liste.
On définie une fonction duree_tri_sorted qui va prendre les valeurs de la liste. On affecte à T1 la valeur du temps à ce moment puis on appelle la fonction sorted qui prend les valeurs de la liste liste (cette fonction va trier la liste automatiquement). On affecte à T2 la valeur du temps à ce moment puis on affecte à la variable duree t2-t1 et on ajoute cette dernière à la liste duree_sorted le #print est en commentaire car c'était pour vérifier que cela marchait. Enfin on mélange la liste.
On définie une fonction duree_tri_insertion qui va prendre les valeurs de la liste. On affecte à T1 la valeur du temps à ce moment. On créé une boucle où j va prendre touts les index (position des valeurs dans la liste) en commençant après le premier de la liste. On affecte à k la valeur de l'élément en position jdans la liste. On affecte à i, i+1. On créé une boucle, tant que i est égale ou supérieur à 0 et que l'élément en position i dans la liste est supérieur à key, alors on affecte à l'élément en position i+1 la valeur de l'élément en position i. On affecte à i, i+1. On affecte à l'élément en position i+1 la valeur de key. Puis on affecte à T2 la valeur du temps à ce moment puis on affecte à la variable duree t2-t1 et on ajoute cette dernière à la liste duree_insertion le #print est en commentaire car c'était pour vérifier que cela marchait. Enfin on mélange la liste.
On définie une fonction duree_tri_selection qui va prendre les valeurs de la liste. On affecte à T1 la valeur du temps à ce moment. On créé une boucle for où i va prendre toutes les valeux index de la liste. On affecte à la variable min la valeur de i. On créé une nouvelle boucle for où j va prendre les valeur de la longueur de la liste à partir de l'élément en position i+1. Si l'élément en position min est supérieur à l'élément en position j, alors on affecte à min la valeur de j. On affecte à la variable tmp la valeur de l'élément en position i dans la liste. On affecte à l'élément en position i la valeur de l'élément en position min. Puis on affecte à l'élément en position min la valeur de tmp. Enfin on affecte à T2 la valeur du temps à ce moment puis on affecte à la variable duree t2-t1 et on ajoute cette dernière à la liste duree_selection le #print est en commentaire car c'était pour vérifier que cela marchait. Enfin on mélange la liste.
On créé une boucle for qui va prendre touts les éléments contunus dans la liste n. On affcete à la variable liste la valeur de la fonction création de liste aléatoire (voir plus haut) qui prend les valeurs de la liste n. On affiche element dan s la console pour vérifier le programme. On appelle la fonction duree_tri_insertion qui va prndre les valeurs de la liste, de même pour les fonctions duree_tri_selection, duree_tri_sort et duree_tri_sorted.
On va importer la blibliothèque matplotlib dans python. On définie la fonction tracer_figure qui va prendre les valeurs contenues dans les liste duree_insertion, duree_selection, duree_sort et duree_sorted mais églement la liste n. Plt c'est l'outil pour tracer la figure, on ajuste la taille de la figure ici avec 16 de haut et 10 de long. On crée un marker qui va être vert et en forme d'étoile dont la légende sera insertion et qui va prendre comme valeurs les éléments contenue dans la la liste duree_insertion. On crée un marker qui va être rouge et en forme d'étoile dont la légende sera selection et qui va prendre comme valeurs les éléments contenue dans la la liste duree_selection. On crée un marker qui va être bleu et en forme d'étoile dont la légende sera sort et qui va prendre comme valeurs les éléments contenue dans la la liste duree_sort. On crée un marker qui va être jaune et en forme d'étoile dont la légende sera sorted et qui va prendre comme valeurs les éléments contenue dans la la liste duree_sorted.
Puis on met en légende sur l'axe des x "nombre d'élément", On fait trouner de 60° ces légends. On met en légende sur l'axe des y "duree"et on met en légende au graphique "La duree des tris". Puis on écrit "plt.legend()" et "plt.show()" pour pouvoir afficher les légendes et afficher le graphique.
Enfin on écrit "if __name__=="__main__":" car dans un programme python c'est le fichier main qui s'execute en premier seulement ici il n'y a pas de fichier main donc c'est le fichier que l'on a qui va s'executer. Pour terminé on demmande de tracer la figure avec les valeurs des listes "duree_insertion", "duree_selection", "duree_sort" et "duree_sorted" avec "tracer_figure(n,duree_insertion, duree_selection,duree_sort,duree_sorted )"et la liste n.