Rien ne sert de modeler, de créer ou de transformer sans les outils adéquats. Que serait un peintre sans pinceaux? Certes, il pourrait utiliser ses doigts, mais encore là, il s'agit d'un outil.

En informatique, par exemple, il existe une multitude d'outils pour créer. On peut créer une multitude d'applications qui vont rendre la vie de tous les jours un peu plus simple (ou un peu plus compliquée, lorsqu'il y a une panne du système). Mais tous ces outils que l'informaticien utilise, si on y regarde bien, finissent toujours par se résumer à une classe d'outil que l'on nomme algorithme. Un algorithme, c'est la description des tâches à effectuer pour produire un résultat à partir de données d'entrée. Lorsqu'on parle de donnée, il n'est pas forcément question de données mathématiques; le mouvement de la souris est une donnée, par exemple.

Le programmeur, si doué soit-il, ne peut malheureusement pas tout créer. Cela représenterait une perte d'énergie considérable, et c'est humainement impensable. En effet, il existe des algorithmes pour lesquels des années de recherches ont été nécessaire. Je pense en particulier aux algorithmes de tri.

Trier un ensemble de nombre ou de chaînes de caractères n'est pas aussi trivial qu'il y paraît. On se heurte rapidement au problème de la durée d'exécution. Il est relativement aisé de concevoir une manière de trier une liste de nombre, mais si cette liste de nombre devient imposante, la durée d'exécution également va croitre. La durée d'exécution en tant que telle ne peut pas être estimée, car elle dépend de l'ordinateur qui va l'effectuer. Par contre, on peut utiliser le nombre de comparaisons pour quantifier la durée d'exécution. Ce nombre va définir, dans le cas des tris, ce qu'on appelle la complexité, notée O(ordre de grandeur).

Lorsqu'on étudie en informatique, il y a forcément un chapitre sur les tris. Généralement, on y étudie: le tri bulle, le tri par insertion, le tri shell (si on a de la chance), le tri "quicksort", le tri fusion (si on est extrêmement chanceux). Les deux premier tris sont les pires solutions, car la complexité est O(n²) (si n est le nombre de données, alors il y aura n² comparaisons). Les trois autres tris sont de complexité O(n log n).

Pourtant, à l'époque de la carte perforée, qui était le seul moyen de programmer, il y avait des machines qui triaient les cartes des malheureux informaticiens maladroits qui échappaient leur paquets de 3000 cartes à terre. Et il y a bien fallu trouver une manière de trier ces cartes rapidement.

Admettons qu'une telle machine est capable d'effectuer 10 comparaisons par secondes. Pour les tris en O(n²), cela fait 3000² = 9,000,000 tris soit 900,000 secondes, soit un peu plus de dix jours pour trier. Sincèrement, un humain serait plus rapide.

Admettons que nous utilisions un tri en O(n log n), ce qui donne environ 10,500 tris, soit environ 17 minutes de tri. Le gain est appréciables. Il existe cependant une petite restriction pour ces tris, il doivent être considérés comme en place. Cette notion ne sera pas approfondie ici.

Cependant, aucun de ces tris n'a été utilisés. C'est le tri par base qui a été choisi, il a une complexité de O(n), ce qui veut dire qu'il lui faudrait seulement cinq minutes pour trier les 3000 fiches...

Évidemment, tout ces calculs sont légèrement faussés. Premièrement dans une machine physique, ce ne sont pas seulement les comparaisons qu'il faut considérer, mais également le nombre de déplacement des cartes. De plus, la complexité du tri par base est, en réalité, plutôt O(nk), où k est la taille moyenne de la clé (le numéro de carte). Pour une clé moyenne de 10 positions, il y aura plutôt 50 minutes de tri.

Ceci dit, si on reporte tous ces algorithmes sur un modèle informatique actuel (une série de nombre en mémoire par exemple), le tri par base reste le meilleur, car il est linéaire, alors que les autres tri sont exponentiels.

Pourtant, jamais il n'ait fait mention de l'usage d'un tel tri dans nos programmes. Dès qu'il s'agit de trier, on pense souvent au quicksort (c'est peut être son nom qui l'a rendu si célèbre...). Pourtant, il existe, pour les nombres, plusieurs tris de complexité linéaire, qu'il serait souvent adéquat d'utiliser.

Donc, plus nous en savons sur les outils qui existent (et qui ne sont pas forcément populaires), plus nous avons de moyens de contrôler ce que nous créons. Mais il n'est pas nécessaire de tout retenir... il suffit de faire le tri dans nos connaissances pour en tirer le meilleur parti.