-
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 second cas, par 200. Même si ce n’est pas le seul critère, cela donne de quoi réfléchir sur le choix de la méthode !

Trier les lignes et les colonnes

L’utilisation d’un tableur amène à se poser d’amusantes questions concernant les inégalités. Quand on dispose d’un tableau contenant plusieurs valeurs, on peut trier chaque colonne (quitte à utiliser une macro-instruction, ou « macro », pour un très grand tableau). On peut ensuite trier chaque ligne. Mais ce classement sur les lignes ne va-t-il pas perturber celui sur les colonnes ? Heureusement, la réponse est non !