Se servir d’un tableur ne signifie pas simplement créer un beau tableau. Vous avez la possibilité de trier les éléments et les données. Pour cela, vous utilisez un algorithme de tri. Seulement, il en existe plusieurs ! La méthode de comparaison va changer entre ces algorithmes. Alors, qu’est-ce qu’un algorithme de tri ? Quels sont les différents types d’algorithmes de tri d’un tableur ? Explications.
Algorithmes de tri : qu’est-ce que c’est ?
Le tri fait partie de notre vie quotidienne. En informatique, c’est pareil ! Les algorithmes de tri sont étudiés dans le cadre de la programmation et du code informatique.
Le fonctionnement des algorithmes de tri
Un tableau contient plusieurs éléments de même type et de même entité. Trier un tableau, c’est répartir les données en plusieurs classes selon certains critères. Chaque élément d’un tableau est rangé en ordre croissant ou décroissant. La méthode de tri peut être différente. L’algorithme de tri par comparaison lit les données par comparaison binaire ou tertiaire. D’autres algorithmes fonctionnent par une procédure d’insertion, de fusion, etc.
La complexité des algorithmes de tri d’un tableur
Deux types de complexité s’imposent aux algorithmes de tri d’un tableau : une complexité temporelle et une complexité spatiale.
La complexité temporelle
La complexité temporelle mesure les nombres d’opérations élémentaires effectuées pour trier plusieurs éléments. C’est une estimation du temps d’exécution de l’algorithme. La complexité temporelle détermine les nombres de comparaisons réalisées.
La complexité spatiale
Contrairement à la complexité temporelle, la complexité spatiale détermine la quantité de mémoire dont va avoir besoin l’algorithme pour s’exécuter.
Les différents types d’algorithmes de tri d’un tableur
Les algorithmes n’appliquent pas du tout la même procédure. Certains fonctionnent par comparaison, d’autres par fusion, insertion, etc. D’autres existent encore. Nous vous en présentons quelques-uns.
Le tri à bulle ou le tri par propagation
Le tri à bulle ou le tri par propagation est le moins performant des tris de tableau. Le nom de tri à bulle lui a été donné, car à la fin de chaque itération, le plus grand nombre de chaque sous-suite se déplace vers la droite comme des bulles. L’algorithme passe sur chaque élément de la liste du tableau. Cet élément est comparé à son voisin de droite. Lorsque l’élément de droite est plus petit, les deux éléments permutent. L’élément plus petit se trouve toujours à gauche.
Le tri par sélection
L’algorithme de tri par sélection fonctionne par comparaison. Il est simple, mais souvent inefficace. Il trie dans le tableau le numéro de l’élément le plus petit. L’algorithme sélectionne à chaque étape le plus petit élément de la partie non triée. Il échange cet élément avec le début de la tranche non triée.
Le tri par insertion
L’algorithme de tri par insertion est un des plus simples, mais c’est aussi un des plus lent lorsqu’il y a beaucoup de données. En revanche, il est très efficace avec peu d’éléments. L’algorithme fait une recherche dans le tableau et va passer sur chaque élément à trier et l’insère à sa place. Il va faire une comparaison des éléments courants avec chaque élément trié sur la gauche.
Le tri rapide
L’algorithme du tri rapide fonctionne autour d’un élément central appelé le pivot. Le pivot est généralement le dernier élément du tableau. Il va créer ensuite un sous-tableau. Les valeurs inférieures à celle du pivot vont être déplacées à gauche de ce sous-tableau. Le pivot reste au milieu. Les valeurs supérieures à celle du pivot vont trouver leur place à droite. Il fait partie de la famille des algorithmes “diviser pour régner”.
Le tri par fusion
L’algorithme de tri par fusion est efficace sur de grandes comparaisons de données. Il commence toujours par diviser le tableau en deux éléments égaux. L’algorithme recommence jusqu’à atteindre un seul élément par séparation. Les éléments sont fusionnés en les triant à chaque niveau. C’est un des algorithmes les plus optimisés donc un des plus utilisés. Cet algorithme de tri rapide fait aussi partie des algorithmes “diviser pour régner”.
Le tri par dénombrement
L’algorithme de tri par dénombrement ne fait pas de comparaisons. Il va compter le nombre d’occurrences du tableau. Cet algorithme n’est pas adapté pour le tri de nombres, ou des chaînes de caractères.
Le tri arborescent
C’est un algorithme qui est un des plus lent parmi les plus rapides. Il consiste à insérer les éléments un à un dans un arbre binaire de recherche et ensuite de lire l’arbre selon un parcours plus en profondeur. Cet algorithme demande beaucoup de mémoire en raison de la structure d’arbre binaire à manipuler.
Les différents types d’algorithmes de tri dans un tableur fonctionnent par comparaisons, insertion, sélection, etc. Beaucoup d’autres existent. Pour comparer certains algorithmes, il faut prendre en compte la taille des données à trier et la quantité de mémoire vive disponible.
