Pour cela, il existe de nombreuses méthodes, ou algorithmes. Ces derniers se distinguent par la longueur du code, écrit dans un langage informatique (Python, Fortran, C++, Basic…), mais surtout par leurs performances. En effet, le temps mis pour réaliser un tri est très important : si, pour trier cent données, on a déjà besoin de dix minutes, alors cela va être difficile avec davantage de données ! Un paramètre, appelé complexité temporelle, mesure le nombre d’opérations élémentaires effectuées pour trier les données ; cela fournit, bien sûr, une estimation du temps d’exécution de l’algorithme. Les complexités utilisées sont celle en moyenne (calculée sur toutes les données) et celle dans le pire des cas (calculée dans le cas le plus défavorable des données). Si n est la taille des données, les complexités des algorithmes habituels sont de l’ordre de n2 (on écrit, avec la notation de Landau, que c’est un O(n2)), voire, encore mieux, de l’ordre de n log n (c’est un O(n log n)). Bien sûr, cela ne donne pas la durée précise mais cela indique, par exemple, que si on multiplie le nombre de données par 100, dans le premier cas, la durée de calcul est multipliée par 10 000 et dans le ...
Lire la suite gratuitement