• 4 heures
  • Facile

Ce cours est visible gratuitement en ligne.

Ce cours est en vidéo.

Vous pouvez obtenir un certificat de réussite à l'issue de ce cours.

J'ai tout compris !

Mis à jour le 20/05/2019

Triez des informations

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

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écouvrez tout de suite un des algorithmes de tri les plus connus : le tri à bulles !

Le tri à bulles

Cet algorithme avance 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.

tri_à_bulles(Tableau T)
   pour i allant de taille de T - 1 à 1
       fais quelque chose

Quand 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.

tri_à_bulles(TableauT)
   pour i allant de taille de T - 1 à 1
       si T[i + 1] < T[i]
           echanger_(T[i + 1], T[i])

Ceci 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 :

tri_à_bulles(Tableau T)
   pour i allant de taille de T - 1 à 1
       pour j allant de 0 à i - 1
           si T[j+1] < T[j]
               échanger(T[j+1], T[j])

En Python :

def inter(a_list):
    for i in range(0, len(a_list) - 1):   
        for j in range(0, len(a_list) - 1):
            if a_list[j + 1] < a_list[j]:
                a_list[j+1], a_list[j] = a_list[j], a_list[j+1]
    return a_list

Autres 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 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.

Exemple de certificat de réussite
Exemple de certificat de réussite