Trier des listes (tri à bulles) [Quelques algorithmes classiques]

Trier des listes (tri à bulles)

Objectif

Connaître le fonctionnement d'un algorithme de tri.

Mise en situation

Les tris forment une famille d'algorithmes très classiques, le tri étant très utile pour optimiser les algorithmes de recherche. Mais l'optimisation d'un algorithme de tri lui même est aussi très intéressant, d'autant plus qu'il en existe plusieurs différents. C'est un cas d'école souvent étudié pour comparer la complexité des différents algorithmes. Cependant aujourd'hui, la quasi-totalité des langages de programmation implémentent directement des fonctionnalités de tri en interne, ce qui fait que les algorithmes de tri sont désormais plus de l'ordre de la culture générale que du besoin pratique.

Algorithmes de tri

Il existe de nombreux algorithmes de tri. Chacun ont leurs avantages et leurs inconvénients. Certains sont plus efficaces sur des listes peu mélangées (juste quelques éléments dans le mauvais ordre) d'autres seront plus lents mais ont une complexité en temps qui est moindre. Voici une liste de quelques uns des tris les plus connus :

Tri rapide,
Tri fusion,
Tri par tas,
Tri à bulles,
Tri par insertion,
etc.

Méthode : Tri à bulles

L'idée de ce tri est de faire remonter itérations après itérations les valeurs hautes vers la fin de la liste. On peut voir un analogie avec les gouttes d'huiles remontant petit à petit vers la surface de l'eau. Après la première itération, la valeur maximale sera à la fin de la liste. En parallèle, il est très probable que d'autres valeurs hautes aient avancé légèrement en direction de la fin de la liste. Voici les implémentations JavaScript et Python pour mieux comprendre cela :

/** JavaScript : tri à bulles d'une liste d'âges. */
const ages = [17, 1, 28, 5]
for (let i = ages.length - 1; i > 0; i = i - 1) {
  for (let j = 0; j < i; j = j + 1) {
    if (ages[j + 1] < ages[j]) {
      // Echanger les deux valeurs
      const temp = ages[j + 1]
      ages[j + 1] = ages[j]
      ages[j] = temp
    }
  }
}
console.log(ages)

/** JavaScript : tri à bulles d'une liste d'âges. */
const ages = [17, 1, 28, 5]

for (let i = ages.length - 1; i > 0; i = i - 1) {
  for (let j = 0; j < i; j = j + 1) {
    if (ages[j + 1] < ages[j]) {
      // Echanger les deux valeurs
      const temp = ages[j + 1]
      ages[j + 1] = ages[j]
      ages[j] = temp
    }
  }
}

console.log(ages)

"""Python : Tri à bulles d'une liste d'âges. """
ages = [17, 1, 28, 5]
for i in range(len(ages)-1, 0, -1):
  for j in range(0, i):
    if ages[j+1] < ages[j]:
      # Echanger les deux valeurs
      temp = ages[j+1]
      ages[j+1] = ages[j]
      ages[j] = temp
print(ages)

"""Python : Tri à bulles d'une liste d'âges. """
ages = [17, 1, 28, 5]

for i in range(len(ages)-1, 0, -1):
  for j in range(0, i):
    if ages[j+1] < ages[j]:
      # Echanger les deux valeurs
      temp = ages[j+1]
      ages[j+1] = ages[j]
      ages[j] = temp

print(ages)

Exemple : Déroulement pas à pas

Sachant qu'il y a deux boucles imbriquées, on prend un exemple très simple qui permettra de comprendre rapidement le fonctionnement de ce tri : ages = [17, 1, 28, 5]

Première itération principale, i = 3 :
- Première itération secondaire, j = 0 : ages[0] (= 17) > ages[1] (= 1) donc on échange les deux valeurs et la liste devient [1, 17, 28, 5].
- Deuxième itération secondaire, j = 1 : ages[1] (= 17) < ages[2] (= 28) donc la liste reste [1, 17, 28, 5].
- Troisième itération secondaire, j = 2 : ages[2] (= 28) > ages[3] (= 5) donc on échange les deux valeurs et la liste devient [1, 17, 5, 28].
- j = 3 = i donc la boucle secondaire se termine.
Deuxième itération principale, i = 2 :
- Première itération secondaire, j = 0 : ages[0] (= 1) < ages[1] (= 17) donc la liste reste [1, 17, 5, 28].
- Deuxième itération secondaire, j = 1 : ages[1] (= 17) > ages[2] (= 5) donc on échange les deux valeurs et la liste devient [1, 5, 17, 28].
- j = 2 = i donc la boucle secondaire se termine.
Troisième itération principale, i = 1 :
- Première itération secondaire, j = 0 : ages[0] (= 1) < ages[1] (= 5) donc la liste reste [1, 5, 17, 28].
- j = 1 = i donc la boucle secondaire se termine.
i = 0 donc la boucle principale se termine

Dans ce déroulement, on constate nettement le concept de bulles dans la première itération principale : 28 remonte « à la surface » et finit en dernière position tandis que 17 remonte légèrement et atteindra sa position finale à l'itération principale suivante.

Complément : Complexité du tri à bulles

La complexité en temps de ce tri est O(n²). On peut voir très clairement ce qui explique cette complexité grâce à la boucle imbriquée. Il ne fait pas partir des tris les plus rapides tel que le tri fusion qui est en O(n*log(n)).

Attention : Ne jamais implémenter un tri soi-même

Il est important pour un développeur de connaître des algorithmes de tri car ces algorithmes mettent en œuvre de manière très élégante des concepts algorithmiques majeurs. Ils font partie de la culture générale des développeurs.

En revanche, il faut jamais implémenter ce type d'algorithme soi-même.

La quasi-totalité des langages possède des fonctions de tri déjà implémentées. Celles-ci ne proposent même pas à l'utilisateur de choisir le tri à utiliser car elles sont optimisées pour utiliser le tri optimal selon la liste fournie. Voici comment faire en JavaScript et en Python :

const ages = [18, 6, 82]
ages.sort()

const ages = [18, 6, 82]
ages.sort()

ages = [18, 6, 82]
ages.sort()

ages = [18, 6, 82]
ages.sort()

À retenir

Il existe de nombreux algorithmes de tri avec chacun leurs avantages.
Il ne faut pas implémenter d'algorithme de tri soi-même car les langages ont déjà des fonctions de tri parfaitement optimisées.