Le tri par bulles est un algorithme simple qui est utilisé pour trier un ensemble donné de n éléments fournis sous forme de tableau avec n nombre d’éléments. Bubble Sort compare tous les éléments un par un et les trie en fonction de leurs valeurs.
Si le tableau donné doit être trié par ordre croissant, alors le tri à bulles commencera par comparer le premier élément du tableau avec le deuxième élément, si le premier élément est supérieur au deuxième élément, il échangera les deux éléments, puis passera à comparer le deuxième et le troisième élément, et ainsi de suite.
Si nous avons un total n éléments, puis nous devons répéter ce processus n-1 fois.
C’est ce qu’on appelle le tri à bulles, car à chaque itération complète, le plus grand élément du tableau donné, bouillonne vers la dernière place ou l’indice le plus élevé, tout comme une bulle d’eau monte à la surface de l’eau.
Le tri s’effectue en parcourant tout les éléments un par un et en le comparant avec l’élément adjacent et en les échangeant si nécessaire.
REMARQUE: Si vous n’êtes pas familier avec le tri dans la structure de données, vous devriez fi Apprenez d’abord ce que le tri est à savoir sur les bases du tri.
Implémentation de l’algorithme de tri à bulles
Voici les étapes impliquées dans le tri à bulles (pour trier un tableau donné par ordre croissant):
- En commençant par le premier élément (index = 0), comparez l’élément actuel avec l’élément suivant du tableau.
- Si l’élément actuel est supérieur à l’élément suivant du tableau, permutez-les.
- Si l’élément actuel est inférieur à l’élément suivant, passez à l’élément suivant. Répétez l’étape 1.
Considérons un tableau avec des valeurs {5, 1, 6, 2, 4, 3}
Ci-dessous, nous avons un représentation illustrée de la manière dont le tri par bulles triera le tableau donné.
Ainsi, comme nous pouvons le voir dans la représentation ci-dessus, après le première itération, 6 est placé au dernier index, qui est la bonne position pour celui-ci.
De même après la deuxième itération, 5 sera à l’avant-dernier index, et ainsi de suite.
Il est temps d’écrire le code pour le tri des bulles:
Bien que la logique ci-dessus trie un tableau non trié, l’algorithme ci-dessus n’est toujours pas efficace car, selon la logique ci-dessus, le for continuera à s’exécuter pendant 6 itérations même si le tableau est trié après la deuxième itération.
Nous pouvons donc clairement optimiser notre algorithme.
Algorithme de tri de bulles optimisé
Pour optimiser notre bubb l’algorithme de tri, nous pouvons introduire une flag pour contrôler si les éléments sont échangés à l’intérieur de la boucle interne for.
Par conséquent, dans la boucle interne for, nous vérifions si un échange d’éléments a lieu ou non, à chaque fois.
Si pour une itération particulière, aucun échange n’a eu lieu place, cela signifie que le tableau a été trié et que nous pouvons sauter hors de la boucle for, au lieu d’exécuter toutes les itérations.
Considérons un tableau avec des valeurs {11, 17, 18, 26, 23}
Ci-dessous, nous avons une représentation graphique de la façon dont le tri optimisé des bulles triera le tableau donné.
Comme nous pouvons le voir, lors de la première itération, un échange a eu lieu, c’est pourquoi nous avons mis à jour notre valeur flag à 1, par conséquent, l’exécution entre à nouveau dans la boucle for. Mais dans la deuxième itération, aucun échange ne se produira, donc la valeur de flag restera 0, et l’exécution sortira de la boucle.
Dans le code ci-dessus, dans la fonction bubbleSort, si pour un cycle complet unique de j itération (boucle interne for), aucun échange n’a lieu, puis flag restera 0 et ensuite nous sortirons des boucles for, car le tableau a déjà été trié.
Analyse de complexité du tri à bulles
Dans le tri à bulles, n-1 les comparaisons seront effectuées lors du premier passage, n-2 en 2ème passe, n-3 en 3ème passe et ainsi de suite. Donc le nombre total de comparaisons sera,
(n-1) + (n-2) + (n-3) + ….. + 3 + 2 + 1Somme = n (n- 1) /2i.e O (n2)
Par conséquent, la complexité temporelle du tri à bulles est O (n2).
Le principal avantage du tri à bulles est la simplicité de l’algorithme.
La complexité de l’espace pour Bubble Sort est O (1), car un seul espace mémoire supplémentaire est requis, c’est-à-dire pour la variable temp.
De plus, la complexité temporelle du meilleur cas sera O (n), c’est lorsque la liste est déjà triée.
Voici la complexité temps et espace de l’algorithme de tri à bulles.
Maintenant que nous avons appris l’algorithme de tri à bulles, vous pouvez également consulter ces algorithmes de tri et leurs applications:
- Tri par insertion
- Tri par sélection
- Tri rapide
- Tri par fusion
- Tri par tas
- Tri par comptage
