Programme Algorithmes de TRI
Création d'un programme algorithmes de tri
Afin d'évaluer l'efficacité des algorithmes de tri, nous avons procéder à un programme contenant plusieurs de ces tris.
​
Nous avons d'abord fait deux tris " sort " et " sorted ".
Objectifs attendus :
-Ajoutez plusieurs tris (minimum 3)
- Obtenir un graphique.
-Ajoutez des modèles si possible.
Graphique donné par le professeur:
Fonction modèle (facultatif)
On génère d'abord une liste aléatoirement et on crée une liste pour chaque tri ( on rajoutera au fur et à mesure différents tris).
* On définit ensuite la fonction "creation_de_liste".
* append() nous permettra d'ajouter des éléments dans la liste vide ( n_liste.append(i*1000) ).
* On prendra une petite valeur comme 1000 pour éviter que le programme soit lent ou bug.
* Pour comparer l'efficacité et la rapidité des tris, on définit deux fonctions, une " duree_tri_sort " qui prendra en paramètre (liste) ainsi que " duree_tri_sorted" qui prendra en paramètre (liste). Comme leur nom l'indique, on obtiendra la durée des tris.
* On utilisera à nouveau append() mais on rajoutera une nouvelle fonction " random.shuffle(liste) " qui mélangera nos listes, changera la position des éléments de la liste.
t1=time()
t2=time() exprime la différence entre deux instants.
duree=t2-t1
* Afin de réaliser notre objectif, je crée un nouvel algorithme de tri, le tri d'insertion.
* Je fais le même procédé appliqué sur les autres tris pour avoir le temps d’exécution et l'efficacité de ce-dernier.
Erreurs rencontrées:
​
En créant ce tri d'insertion, mon programme était incomplet, il s’arrêtait au " return L" car je n'avais pas ajouté les comparaisons de temps.
* for i in range prendra toutes les valeurs entre 1 et 11.
* print(i) affiche i
* On affecte L à creation_de_liste()
Erreurs rencontrées:
​
En exécutant le programme, un message d'erreur s'affichait. Après avoir régler les problèmes du programme, il ne voulait toujours pas s’exécuter.
Même après avoir rechercher sur internet, je n'y arrivais pas. Avec l'aide du professeur, je remarque l'erreur.
Je n'avais afficher que duree_tri_sort() sans avoir afficher les autres tris rajoutés après.
​
* On finit par définir la fonction tracer_figure qui prend en paramètre listesort, listesorted, listeinsertion,nliste ( soit toutes les listes de tri que l'on a ajouté jusqu'ici ). Cette fonction nous permettra d'afficher un graphique.
* On affichera par la suite des points de différentes couleurs à l'aide de plt.plot ( permet de tracer les graphes de fonctions ) pour connaître l'efficacité et la rapidité de chaque tri.
​
Erreurs rencontrées :
​
Le graphique ne voulait pas s'afficher et renvoyait le même message d'erreur précédemment.
Après plusieurs réflexions, l'erreur était que la ligne plt.plot était mal écrite, il manquait des données.
Après avoir fini la programmation, nous devrions obtenir un graphique ressemblant à cela.
Nous avons atteint notre objectif qui était de créer un graphique avec minimum 3 tris ( sans modèle ).
Conclusion:
On remarque que le tri sort et le tri sorted sont à 0 sur le graphique qu'importe la valeur donnée. Cela voudrait dire que ces tris sont tellement rapides et efficaces qu'ils semblent être à la durée 0 ( mais ne sont pas tout à fait ou toujours à 0 ). En revanche, la durée du tri d'insertion continue d'augmenter. Plus la valeur est grande, plus la durée de l'exécution du tri augmente.
Donc, le tri d'insertion est beaucoup plus lent que le tri sort et le tri sorted.
​
Il sera alors préférable d'utiliser les tris sort et sorted que le tri d'insertion.