Nous avons vu que les algorithmes nous permettaient de résoudre des problèmes plus ou moins complexes. Un des problèmes les plus répandus consiste à trier les informations. Cela vous semble facile à faire ? Et pourtant ! Il ne nous faut pas seulement trier les informations, mais également trouver la manière la plus efficace de le faire.
Trier une suite de 10 nombres du plus petit au plus grand n’est effectivement pas très long. Mais qu’en est-il lorsque nous avons 100 000 nombres à trier ? Que se passe-t-il lorsque vous vous appelez Google et que vous devez trier plusieurs centaines de gigaoctets d’e-mails ?
Les algorithmes de tri sont l’essence même de l’algorithmique. En effet, nous souhaitons souvent réorganiser des données pour les manipuler autrement. Il est donc essentiel d’en savoir un peu plus.
Découvrons ensemble un des algorithmes de tri les plus connus : le tri à bulles !
Le tri à bulles
Cet algorithme progresse dans une liste d’éléments. Il compare les données deux à deux et les échange si la première valeur est plus élevée que la seconde. Il fait cela pour toutes les paires d’éléments dans une liste, puis recommence au début jusqu’à ce que toutes les paires soient dans le bon ordre.
Faisons une démonstration avec des livres ! Nous avons tous eu un jour ou l’autre à trier notre bibliothèque, que ce soit par ordre alphabétique, par auteur ou par hauteur. Pour cette démonstration, disons que nous trions les livres par hauteur.
Nous saisissons le premier livre et le comparons au suivant. S’il est plus grand, nous les échangeons. Sinon, nous les laissons ainsi.
Quand nous avons fini de parcourir tous les livres une première fois, le plus grand se trouve bien à la fin. Nous pouvons alors recommencer un tour de boucle pour placer l’élément suivant.
Et ainsi de suite jusqu’à ce que la bibliothèque soit triée !
Comment l’écririons-nous en pseudo-code ?
Nous commençons par écrire une fonction qui va parcourir tous les livres, un à un. Vous connaissez déjà cette structure : il s’agit d’une boucle ! Nous allons donc faire 10 tours, puisque nous allons parcourir une liste de 10 livres, mais, pour changer, de la dernière case à la première.
Algorithme Tri_a_bulle(tableau)
taille ← Taille du tableau
Pour i allant de taille - 1 jusqu’à 1 :
…
Fin Pour
FinQuand nous sommes dans la boucle, nous intervertissons les livres si le second est plus grand que le premier. Nous pouvons donc utiliser les structures conditionnelles que nous avons déjà vues.
Algorithme Tri_a_bulle(tableau)
taille ← Taille du tableau
Pour i allant de taille - 1 jusqu’à 1 :
Si tableau[i] < tableau[i-1] :
echanger(tableau[i], tableau[i-1])
Fin Si
Fin Pour
FinCeci est déjà très bien, mais ce n’est pas suffisant. Actuellement, chaque item a bougé d’une place, mais n’est pas vraiment remonté jusqu’à la fin. Alors, comment faire ?
Si nous réfléchissons bien, il faut faire un nombre de boucles correspondant au nombre d’items restant à trier dans la liste au carré.
Prenons l’exemple du premier livre. S’il s’agit du plus grand, notre algorithme devra effectuer 9 tours de boucle afin de le positionner à la fin. Mais une fois que le livre est en place, il sait qu’il n’a pas à aller jusqu’à la fin. Il peut donc effectuer 8 tours de boucle, puis 7, puis 6 et ainsi de suite jusqu’à 1.
En pseudo-code, nous allons le représenter ainsi :
Algorithme Tri_a_bulle(tableau)
taille ← Taille du tableau
Pour i allant de taille - 1 jusqu’à 1 :
Pour j allant de 0 jusqu’à i - 1
Si tableau[j+1] < tableau[j] :
echanger(tableau[j+1], tableau[j])
Fin Si
Fin Pour
Fin Pour
FinAutres algorithmes de tri
Le tri à bulles est le plus connu de tous, mais pas le plus efficace. D’ailleurs, nous-mêmes, lorsque nous devons trier des livres, nous ne comparons pas deux livres et ainsi de suite. Nous utilisons d’autres algorithmes.
Si nous avons une grande bibliothèque, nous pouvons décider de la diviser en plusieurs unités plus petites afin de les trier séparément, et ensuite de les fusionner. Ou bien, nous nous disons : je mets les livres les plus grands et les plus petits au début, en même temps.
Bref, nous avons chacun notre stratégie. Il existe trop d’algorithmes de tri différents pour tous les expliquer ici. Je vous propose un tableau résumant les types de tri les plus utilisés :
Type de tri | Description |
Tri par insertion | Le tri par insertion considère chaque élément du tableau, et l'insère à la bonne place parmi les éléments déjà triés. |
Tri par sélection | Le tri par sélection est un algorithme de tri qui sélectionne à chaque itération le plus petit élément d'une liste non triée, et place cet élément au début de la liste non triée. |
Tri par tas | Le tri par tas débute par la construction d'un tas sur le tableau d'entrée. Comme l'élément maximum du tableau est stocké à la racine, on peut le placer dans sa position finale correcte en l'échangeant avec le dernier élément du tableau. |
Tri par fusion | Le tri par fusion fonctionne sur le principe de diviser pour mieux régner. Le tri par fusion décompose à plusieurs reprises une liste en plusieurs sous-listes jusqu'à ce que chaque sous-liste se compose d'un seul élément, et fusionne ces sous-listes de manière à obtenir une liste triée. |
Je vous conseille néanmoins de regarder cette liste non exhaustive des différents tris proposés sur cette page Wikipédia, et d’en lire quelques définitions afin de mieux les comprendre.
À vous de jouer
Contexte
Rappelez-vous que la porte à l’arrivée du labyrinthe est verrouillée à l’aide de 3 clés. Ces clés sont numérotées de 1 à 3. La clé qui a le numéro 1 correspond au trou de serrure le plus haut sur la porte, la clé qui a le numéro 2 à la suivante en dessous, et ainsi de suite. Pour éviter de perdre du temps à l’arrivée, il serait intéressant de trier le sac à l’aide des numéros des clés par ordre croissant, afin de les sortir dans l’ordre.
Consigne
Vous devez écrire le pseudo-code d’un algorithme de tri par insertion. Un tri par insertion compare les valeurs deux à deux, en commençant par la deuxième valeur de la liste. Si cette valeur est supérieure à la valeur située à sa gauche, aucune modification n'est apportée. Sinon, cette valeur est déplacée à plusieurs reprises vers la gauche jusqu'à ce qu'elle rencontre une valeur inférieure à elle.
Votre objectif :
Enregistrer la taille du tableau dans une variable
N.Parcourir le tableau de la deuxième case à la fin du tableau.
Enregistrer temporairement l'élément courant de votre itération.
Comparer cet élément avec tous les éléments de la sous-liste triée.
Décaler tous les éléments de la sous-liste supérieurs à la valeur à trier.
Insérer la valeur temporaire.
Répéter jusqu'à ce que la liste soit triée.
Vérifiez votre travail
Voici le résultat à obtenir à l'issue de l'exercice :
Algorithme Tri_par_insertion(tableau)
N ← Taille du tableau
Pour i allant de 1 jusqu’à N - 1 :
x ← tableau[i]
j ← i
Tant que j > 0 ET tableau[j-1] > x :
tableau[j] ← tableau[j-1]
j ← j - 1
Fin Tant que
tableau[j] ← x
Fin Pour
FinEn résumé
Le tri des données est une tâche importante et largement utilisée lors du développement de logiciels.
Il existe différents types de tri, tels que le tri à bulles, le tri par sélection, le tri par insertion et bien d’autres.
Tous les algorithmes ne sont pas efficaces pour un même problème, il faudra donc choisir l’algorithme de tri adapté au problème.
Je vous ai expliqué précédemment que tous les algorithmes ne sont pas adaptés à toutes les situations. Mais pourquoi ? En fonction du problème, le temps peut être plus ou moins long. On parle alors de la complexité de l’algorithme. Nous allons voir dans le prochain chapitre comment la calculer.
