Tri à bulles est considéré comme l’un des algorithmes de tri les plus simples qui fonctionne en échangeant à plusieurs reprises les éléments adjacents s’ils sont dans le mauvais ordre. Avec un algorithme de tri par bulles, vous serez en mesure de voir que le plus grand élément (en supposant que nous trions du plus petit au plus grand) « bouillonnera » jusqu’en haut de la liste ou du tableau.

Exemple:
Supposons que nous voulions trier une liste ou un tableau d’éléments dans l’ordre croissant (du plus petit au plus grand): List = (3,1,2)

Puisqu’aucun échange n’a eu lieu, cela nous indique que le tableau est déjà triés par ordre croissant!

Meilleur cas

Maintenant, essayons à nouveau ce même algorithme mais cette fois en utilisant le meilleur scénario, c’est-à-dire lorsque les éléments sont déjà triés dans l’ordre ( croissant) que nous aimerions.

Comme aucun échange n’a eu lieu, nous avons terminé, et l’algorithme n’a fait que 2 comparaisons et le nombre d’éléments dans le tableau que nous appellerons n = 3. Nous pouvons donc voir que pour n éléments dans le meilleur des cas de cet algorithme ne prendront que n-1 comparaisons, n-1 = O (n)

La procédure ou l’algorithme que nous avons utilisé est ci-dessous:

Cet algorithme utilise un drapeau pour dire si les éléments ont été échangés ou non , qui permet au meilleur cas de l’algorithme de tri à bulles d’être O (n) au lieu de O (n²) comme une autre implémentation du tri à bulles.

L’algorithme ci-dessus
Pire cas = O (n²)
Meilleur cas = O (n)

Jetons un œil à une implémentation différente de l’algorithme de tri à bulles:

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2 for j = A.length downto i + 1
3 if A < A
4 exchange A with A

L’algorithme ci-dessus
Pire cas = O (n²)
Meilleur cas = O (n²)

Pire cas

Trions un tableau ou une liste = (3,2,1) ce serait le pire des cas où la liste est dans l’ordre complètement opposé à celui que nous souhaitons (par ordre croissant) en utilisant l’algorithme ci-dessus.

Premier passage:
(3,2,1) – > Comparez les éléments 3 & 2
(2,3 , 1) – > Swap 3 & 2 depuis 2 < 3
( 2,3,1) – > Comparez les éléments 3 & 1
(2,1,3) – > Swap 1 & 3 depuis 1 < 3

Deuxième passe:
(2,1,3) – > Comparez les éléments 2 & 1
(1,2,3) – > Swap 2 & 1 depuis 1 < 2
(1,2,3) – > Comparez les éléments 2 & 3
(1,2,3) – > Aucun SWAPPING nécessaire depuis 2 < 3

Nous avons maintenant fini de parcourir les deux boucles, le tableau doit donc être trié par ordre croissant.

Remarquez que nous avons fait 4 comparaisons dans le deuxième exemple ci-dessus, et le nombre d’éléments du tableau que nous appellerons ‘n’ = 3, donc le nombre de comparaisons effectuées est (n-1) ², et (n-1) ² = O (n²)

Un excellent livre pour vous préparer aux interviews de codage / programmation s’appelle cracking the coding interview. Cela vous aidera à vous familiariser avec les algorithmes de tri et la résolution de problèmes, alors assurez-vous de le vérifier!

Merci d’avoir lu cet article, j’espère qu’il vous sera utile à tous! Continuez à apprendre, et si vous souhaitez plus de vidéos d’analyse d’algorithmes, veuillez visiter et vous abonner à mes chaînes YouTube (randerson112358 & compsci112358)

Consultez les informations suivantes pour plus de contenu / vidéos sur l’analyse et la programmation d’algorithmes:

Chaîne YouTube:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:

Site Web:

Tutoriels vidéo sur la relation de récurrence:

Tutoriel vidéo sur l’analyse des algorithmes:

Twitter: