Analyse de la complexité théorique
0.002 millisecondes : le temps que peut mettre un algorithme pour trier un tableau
Analyse de la complexité théorique
Imaginez... Vous êtes face à un tableau de 100 cases avec, à l'intérieur, 100 nombres différents qui ont été disposés aléatoirement. Votre but est de trier tous les nombres de ce tableau dans l'ordre croissant. Combien de temps mettrez-vous ?
Un ordinateur réalise le tri en moins d'une milliseconde ! Et si nous changions la taille ? Supposons que maintenant votre tableau possède un million de cases avec donc un million de nombres différents à trier. Et bien pour un ordinateur, le temps se compte encore en millisecondes.
Ce projet, réalisé en binôme, nous a été donné lors de l'étude de la complexité algorithmique à la faculté. L'objectif était d'implémenter, avec le langage de programmation C, quelques algorithmes de tri (9 dans notre cas) et de tester leur temps moyen de tri sur 15 tailles de tableaux différentes. De plus, les algorithmes devaient réaliser leur tri 20 fois pour une taille de tableau. Soit un total de 20 x 15 tris pour chaque algorithme. Lorsqu'un tri est effectué sur les 20 tableaux d'une même taille, nous calculons, grâce à un autre programme réalisé, son temps moyen de tri sur les 20 tableaux. Une fois que les 15 tailles ont été traitées, on répertorie les temps moyens pour chaque taille de tableau et on établie des graphiques afin d'obtenir des courbes comparatives.
Voici les différents algorithmes de tri qui ont été implémentés :
- Le tri par insertion séquentielle
- Le tri par insertion séquentielle avec une liste chaînée
- Le tri par insertion dichotomique
- Le tri par sélection-permutation
- Le tri à bulles
- Le tri par fusion
- Le tri rapide
- Le tri à l'aide d'arbres binaires de recherche
- Le tri par tas
Parmi ces tris, il y en a des "lents" (moins performants) et des "rapides" (plus performants). Les 5 premiers sont des tris "lents" et les 4 derniers sont des tris "rapides". Dans notre projet, nous avons choisi d'arrêter les algorithmes qui mettent plus de 5 minutes à trier les 15 tailles de tableaux. Il se trouve que dans nos résultats finaux, tous les tris "lents" prennent plus de 5 minutes pour trier les 15 tailles. Les tris "rapide", en revanche, prennent moins de 5 minutes. La comparaison des courbes des graphiques obtenues révèle l'efficacité de chaque algorithme.
Le rapport contenant les données, les graphiques et les résultats est disponible ci-dessous.