Le tri à bulles expliqué

Tout comme la façon dont les bulles montent du bas d'un verre, le tri des bulles est un algorithme simple qui trie une liste, permettant aux valeurs inférieures ou supérieures de remonter vers le haut. L'algorithme parcourt une liste et compare les valeurs adjacentes, en les échangeant si elles ne sont pas dans le bon ordre.

Avec une complexité dans le pire des cas de O (n ^ 2), le tri par bulles est très lent par rapport à d'autres algorithmes de tri comme le tri rapide. L'avantage est qu'il s'agit de l'un des algorithmes de tri les plus faciles à comprendre et à coder à partir de zéro.

Exemple:

let arr = [4, 2, 6, 3, 9]; let sorted = false while(!sorted) { sorted = true for(var i = 0; i < arr.length; i++) { if(arr[i] < arr[i - 1]) { let temp = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = temp; sorted = false; } } }

Parcourez d'abord la liste:

  • En commençant par [4, 2, 6, 3, 9], l'algorithme compare les deux premiers éléments du tableau, 4 et 2. Il les échange car 2 <4:[2, 4, 6, 3, 9]
  • Il compare les deux valeurs suivantes, 4 et 6. Comme 4 <6, elles sont déjà dans l'ordre, et l'algorithme avance: [2, 4, 6, 3, 9]
  • Les deux valeurs suivantes sont également permutées car 3 <6: [2, 4, 3, 6, 9]
  • Les deux dernières valeurs, 6 et 9, sont déjà dans l'ordre, donc l'algorithme ne les échange pas.

Deuxième passage dans la liste:

  • 2 <4, il n'est donc pas nécessaire d'échanger des positions: [2, 4, 3, 6, 9]
  • L'algorithme échange les deux valeurs suivantes car 3 <4: [2, 3, 4, 6, 9]
  • Pas de swap comme 4 <6: [2, 3, 4, 6, 9]
  • Encore une fois, 6 <9, donc aucun échange ne se produit: [2, 3, 4, 6, 9]

La liste est déjà triée, mais l'algorithme de tri à bulles ne s'en rend pas compte. Au lieu de cela, il doit effectuer un passage complet dans la liste sans échanger aucune valeur pour savoir que la liste est triée.

Troisième passage dans la liste:

  • [2, 4, 3, 6, 9] =>[2, 4, 3, 6, 9]
  • [2, 4, 3, 6, 9] =>[2, 4, 3, 6, 9]
  • [2, 4, 3, 6, 9] =>[2, 4, 3, 6, 9]
  • [2, 4, 3, 6, 9] =>[2, 4, 3, 6, 9]

Il est clair que le tri à bulles est loin d'être l'algorithme de tri le plus efficace. Pourtant, il est simple de comprendre et de mettre en œuvre vous-même.

Maintenant, allez vous servir une boisson froide et pétillante - vous le méritez.