Projet 3
Algorithmes de tris
Nous avons crée avec M. Laclaverie un programme permettant de calculer puis comparer dans un tableau les durées d'exécution de temps de tris.
Dans un premier temps avec les deux fonctions natives de python :
Sort et Sorted. Voici a quoi le programme ressemblait au debut.
Je décide de créer dans un premier temps deux listes vides, dans lesquelles viendront se ranger les résultats. Il faut faire attention à bien créer une liste pour chaque tri.
De plus, il faut faut veiller à donner des noms simples aux listes afin de ne pas le modifier légèrement par inadvertance au cours du programme. Une erreur que j'ai rencontré dans la réalisation de mon programme et qui m'a value une perte de temps inutile plus un programme qui manqait de rigueur.
Exemple d'erreur : créer la liste resultats_tri_fusion et l'appeler après avec resultats_tri_par_fusion
​
Première fonction du programme, "creation_de_liste". Comme son nom l'indique elle permet de créer les listes. Ensuite deux nouvelles fonctions. Ces dernières servent à définir la durée du tri.
Une fois cette étape terminée, avec un corps de programme fonctionne.
Je décide de continuer mon programme en y rajoutant d’autres types de tris, tous trouvé sur internet. Le schéma reste le même, seulement il convient de rajouter au début du programme une nouvelle liste vide pour chaque nouveau tris et ainsi d'incrémenter une ligne dans chacune des fonctions sur la même base qu'avec les fonctions natives de python : sort et sorted.
J'ajoute les 3 tris suivants : tri à bulle, tri par sélection, tri par insertion
Lorsque les modifications nécessaires ont été faites voici ce que j'obtenais.
Les cinq listes vides comme annoncé. Car maintenant mon programme fait cinq tris
"Ensuite j'ai suivis un modèle de deux fonctions par tri. La première avec le programme de tri, trouvé préalablement sur internet. Puis le second programme reprenant toujours un nom semblable en y ajoutant la durée. C'est en fait a partir de cette dualité des fonctions que je peux faire exécuter les différent tris se trouvant dans mon programme puis directement les chronométrer".
Pour rappel, les tris ont tous été trouvé sur internet. Toutefois cela ne nous empechera pas de nous plonger dedans afin d'en deduire la ou les lignes qui les rendent plus rapide ou plus lents que les autres
Une fois fini, comme à mon habitude je fait s'exécuter le programme assez régulièrement pour voir si il fonctionne toujours afin de repartir si besoin sur une base fonctionnelle. Puis un gros message rouge s'inscrit de la commande. Je ne l'avais jamais vu et je ne comprenais vraiment pas de quoi il s'agissait.
Comme nous pouvons le voir ci-dessous un message d'erreur apparaissait, voici une difficulté à laquelle j'ai dû faire face. C'était la première fois que je voyais ce message et il s'agissait d'un message concernant un problème aux niveau du remplissage des tableaux.
c'était un message m'indiquant qu'une des listes ne rentrait pas dans mon graphique c'est pourquoi il ne pouvait se générer. Pour pallier à ce problème j'ai fait plusieurs modifications, mis plus de rigueur dans mon programme et voilà qu'il remarchais.
Pour conclure ce programme nous rajoutons deux paragraphes de code. La première, avec le 'for i in range. Il s'agit d'une boucle.Enfin la fin du programme permet toute la partie concernant le graphique. Elle permettra d'afficher différents choses.
Sur le partie des tracés. Toute les lignes avec le ply.plot permettent de tracer quelque chose soit comme au début les points soit comme les courbes. De plus elle permettent de les personnaliser de façon a avoir une graphique avec un meilleur rendement. Des paramètres comme la couleur avec les points , ou encore le symbole représentant les points sur le graphiques avec, mais aussi leur nom inscrit dans la partie supérieure gauche du graphique. Ce sont des lignes très importante qui permettent la représentation de tout le code écrit précédemment. et par conséquent toute la lecture et l'interprétation.
Enfin voilà le programme qui s'exécute et le graphique qui se trace.
Pas besoin d'être un génie pour voir que les fonction les plus rapides sont les natives de python. et que la plus lente, de loin est le tris à bulle suivi du tri par insertion.
​
Mainteant que le programme entier s'est exécuter indépendamment des courbes et des équation on se rend bien comptes que les cinq algorithmes de tris ne vont absolument pas à la même vitesse. On peut donc essayer de conclure mais aussi un peu plus loin que cela malheureusment les tris sort et sorted étant natif de python ne permettent pas de voir le code mais les autres si. Les tris par insertions et sélection ont des programmes simples, en restant relatif. C'est pourquoi j'ai décidé de me plonger dans la lecture de leurs codes afin d'essayer de trouver pourquoi étaient-til plus lents que les autres.
​
Plongeons nous rapidement sur ce dernier. Rappelons que le tri par insertion est très rapide avec des listes courtes. C'est d'ailleurs le plus efficace dans ce cas. Au contraire dans des listes composé de tant d'éléments comme dans notre cas, il rame. Le temps d'exécution dépend de la définition du nombre d'étapes, le nombre d'opération ou le nombre de comparaisons.
Dans son code les lignes
k = tab[i]
j = i-1
le ralentissent drastiquement.
Pour terminer mon programme je fais afficher en plus des points, les courbes avec les équations :
je rajoute une fonction modele dans laquelle j'affecte a x np.array avec un boucle qui prend en parametre les valeur entre 1000 et 11000 avec un pas de 1000. Puis j'affecte à y np.array aussi. Le plt.plot permet d'afficher le label des courbes.
EN parallèle je rajoute dand la fonction tracer_figure une ligne pour chaque fonction avec le modèle avec en paramètre le nom du tris. On se rend compte que lescourbes sont des fonction polynomes de degré deux.
En conclusion les deux fonction de tris natifs de pythons sont les plus rapides avecun temps d'exécution quasi nul. Toutefois d'autres tris comme le tri a bulle ou par insertion ou une courbe de durée exponentielle. Dû aux nombreuses comparaisons et opération.