Etude du temps d'exécution de différents algorithmes de tri
Pour le projet n°3 on doit étudier le temps d'exécution de plusieurs algorithmes de tri .
Dans mon programme j'analyse le temps de 6 algorithmes :
- le tri .sort()
- le tri sorted
- le tri par sélection
- le tri par insertion
- le tri à bulles
- le tri par fusion
Pour ce faire nous partons avec un algorithme permettant de calculer la durée de tri de .sort() :
Avec ce programme on peut voir comment évaluer la durée d'exécution du programme avec t1 - t2.
Il y a une fonction création_de_liste permettant de créer des listes avec des nombres aléatoires entre 0 et 100 et pour un nombre d'éléments de i x 1000
Puis nous avons la fonction qui va calculer le temps d'exécution de la fonction .sort()
À partir de ce programme on doit adapter les algorithmes de tri trouvés sur internet pour qu'ils fonctionnent dans notre programme.
TRI SORTED
TRI PAR INSERTION
TRI A BULLES
TRI PAR SELECTION
TRI PAR FUSION
Après avoir adapté chaque algorithme au programme de calcul de la durée des temps d'exécution de plusieurs tris différents.
On modifie la boucle du premier programme pour appeler 10 fois toutes les fonctions de tri. Ensuite avec la fonction "modele" on va créer les modèles de courbes pour chaque algorithme de tri.
Pour tracer dans un graphique les courbes représentatives des temps d'exécution des tris on crée une fonction "tracer_figure" qui peut fonctionner grâce à l'importation de la bibliothèque "mathplotlib.pyplot" qui est symbolisé par "plt."
Après l'exécution du programme on obtient un graphique avec les nuages de points et les courbes représentatives de chaque tri permettant ainsi de les comparer :
Mon programme ne comportant que six tris, de plus pour éviter que l'exécution soit trop longue à cause des tris lents comme le tri par insertion ou bien le tri a bulle on a réduit le taille des listes ce qui empêche une conclusion correcte. On ne peut pas savoir quel est le tri le plus rapide. Pour rétrécir les quantités de potentiels "tri le plus rapide" on nous a fourni un document graphique plus précis que celui produit par mon programme.
Avec le deuxième graphique on peut voir que les tris les plus rapides sont :
- le tri sort
- le tri par fusion
- le tri sorted
- le tri rapide
On ne peut toujours pas nommer le tri le plus rapide
Pour trouver quel est le tri le plus rapide j'ai enlevé de mon programme les tris lents comme le tri à bulles, etc. Puis j'ai exécuté le programme avec une quantité de valeur dans les listes, elles vont de 100 mile à 1 million :
Cela donne le tableau suivant.
On peut voir que le tri par fusion et plus lent que les deux autres quand la quantité a trié est plus grande. Je répète cette opération avec les deux tris restants.
Le nombre d'éléments par liste va maintenant de 150 mile a 15 millions.
Cela donne le graphique suivant.
On voit que l'on ne peut pas vraiment dire lequel des tris sort et sorted est le plus rapide mais on peut voir que le tri sorted semble plus régulier que le tri sort. Mais on ne peut pas dire que l'un est plus efficace que l'autre dans le tri de liste.