LILA
Second projet: LES DIFFERENTS TRIS
Au cours des différentes séances nous avons pu créer différents tris. On a pu s'aider d'internet, et le professeur nous a aussi aidé. Différents problèmes sont apparus lors de la création du programme notamment:
- Pour les fonctions "sort" et "sorted" la console affichait 0 à chaque fois car les nombres étaient trop petits.
- Pour des nombres trop grands le temps d'exécution est trop long donc on pensait que le programme ne s'exécutait pas.
- Un autre problème est survenu lorsqu'à la place de mettre "duree" il y avait "liste". Ce qui a crée des listes de listes et non pas des listes dans la durée. Pour python ce n'est pas faux mais ce n'est pas ce que l'on cherche à faire.
_PNG.png)
Dans un premier temps il faut importer des extensions de fonctions (des modules) qui ne sont pas déjà dans python. C'est-à-dire une bibliothèque pour calculer le temps "from time import", une autre pour calculer aléatoirement, une autre pour des fonctions mathématiques "matplotlib.pyplot" et enfin une dernière pour afficher un graphique "numpy".
Il faut ensuite créer des listes vides pour les résultats des différents tris qui seront calculés par la suite dans le programme.
Définition de la fonction creation_de_liste en ne mettant rien en paramètre.
liste est une liste vide avec:
Pour n_liste on ajoute i*1000.
Itère les instructions avec k prenant chaque valeur dans la liste
(i*1000).
Pour k, liste.append va prendre en paramètre random.randint qui va prendre aléatoirement les nombres de 0 à 99.
Définition de la fonction duree_tri_sort prenant en paramètre liste.
t1 est égal au premier temps.
t2 est égal au deuxième temps.
La duree sera égale au résultat du temps 1 moins le résultat du temps 2.
On ajoute à sort les résultats du tri la duree trouvée.
La liste est mélangée aléatoirement.
Pour le tri sorted le paragraphe ressemble beaucoup au tri sort. Cependant pour la durée du tri sorted on mettra que la liste triée sera égale à sorted avec en paramètre liste.
A l'aide du programme du prof pour la durée du tri par insertion on peut dire qu'on définit duree_tri_par_insertion qui prend en paramètre liste.
Après une première indentation:
t1 est égal au premier temps.
N est égal à la longueur de la liste L.
Itère les instructions avec n prenant chaque valeur dans la liste ( de 1 à N).
Seconde indentation:
La clé est égale à la liste n.
Et j est égal à n-1,
Troisième indentation:
Tant que j sera supérieur ou égal à 0, la liste j sera supérieure à la clé.
Ce qui veut dire la liste j+1 est égale à la liste j.
Donc j=j-1
t2 est égal au deuxième temps.
La duree sera égale au résultat du temps 1 moins le résultat du temps 2.
On ajoute au tri par insertion les résultats de la duree.
On mélange aléatoirement la liste L.
Itère les instructions avec i prenant chaque valeur dans la liste ( de 1 à 11).
On affiche la liste i.
A la place d'écrire creation_de_liste il sera écrit L.
Les durées de chaque tri avec à chaque fois, en paramètres, la liste L.
On définit la fonction tracer_figure en prenant en paramètre chaque liste (plt.figure).
Avec plt.plot définition de la taille du graphique,
Définition de la couleur, de la légende de la liste ainsi que son marqueur pour chaque tri de liste.
Les abscisses sont n et les ordonnées sont Durée.
Le titre du graphique est: Durée versus n.
Pour finir, pour tracer la figure, on écrit tracer_figure qui va donner les résultats en mettant tous les résultats de chaque liste (resultats_sort...).
Conclusion:
Pour conclure on peut dire que les différents tris ne mettent pas le même temps d'exécution pour un même nombre. Certains tris sont plus efficaces lorsque l'on a peu de nombres à trier et inversement, moins efficaces lorsque l'on a beaucoup de nombres à trier. En effet pour i*1000 pour les trois tris on peut voir que sort et sorted ont un temps d'exécution similaire. Au contraire, le tri par insertion met beaucoup plus de temps. C'est pour cela que l'on ne peut pas mettre de nombres trop grands sinon le temps d'exécution du tri par insertion serait beaucoup trop long.
Programme entier
