Les différence principale entre le tri à bulles et le tri par insertion est que Le tri à bulles effectue le tri en vérifiant les éléments de données voisins et en les échangeant s'ils sont dans le mauvais ordre tandis que le tri par insertion effectue le tri en transférant un élément vers un tableau partiellement trié à la fois.

Un algorithme est une séquence d'étapes pour résoudre un problème. Le tri est une opération courante à effectuer sur un ensemble de données. Il existe différents algorithmes pour trier un ensemble de données. Deux d'entre eux sont le tri à bulles et le tri par insertion. De plus, ces deux algorithmes sont considérés comme de simples algorithmes de tri.

Algorithme, tri à bulles, tri par insertion

Qu'est-ce que le tri à bulles

Le tri à bulles est l'algorithme de tri le plus simple. L'algorithme trie les éléments en comparant les paires adjacentes à la fois.

Considérez l'exemple suivant:

40 30 10 70 50 20 60

Dans le tri à bulles, nous comparons des éléments voisins.

Premièrement, nous considérons 40 et 30. 30 est inférieur à 40. Nous pouvons donc échanger ces deux nombres.

30 40 10 70 50 20 60

Maintenant, nous pouvons considérer 40 et 10. 10 est inférieur à 40. Nous pouvons donc échanger ces deux nombres.

30 10 40 70 50 20 60

Maintenant, nous pouvons considérer 40 et 70. Comme 70 est supérieur à 40, il n'est pas nécessaire d'échanger les nombres.

Ensuite, nous considérons 70 et 50. 50 est inférieur à 70. Nous pouvons donc échanger ces deux nombres.

30 10 40 50 70 20 60

Ensuite, nous pouvons considérer 70 et 20. Comme 20 est inférieur à 70, nous pouvons échanger ces deux éléments.

30 10 40 50 20 70 60

Maintenant, nous pouvons considérer 70 et 60. 60 est inférieur à 70. Par conséquent, nous devons échanger ces deux nombres.

30 10 40 50 20 60 70

Maintenant, vous pouvez voir que le plus grand élément de l'ensemble de données est maintenant à la fin. Autrement dit, à la fin du premier passage, le plus gros élément est déjà trié. Par conséquent, la prochaine fois, nous n'aurons pas à considérer 70 car il est déjà trié. Nous n'avons qu'à vérifier les six autres éléments.

10 30 40 50 20 60 70

Maintenant, nous considérons 30 et 40. 40 est supérieur à 30. Il n'est pas nécessaire d'échanger les nombres. Ensuite, nous pouvons considérer 40 et 50. Comme 50 est supérieur à 40, il n'est pas nécessaire d'échanger.

Maintenant, considérons 50 et 20. 20 est inférieur à 50. Donc, nous échangeons ces deux nombres.

10 30 40 20 50 60 70

Maintenant, considérons 50 et 60. Il n'est pas nécessaire d'échanger. A la fin de la deuxième passe, le deuxième élément le plus grand est trié. Autrement dit, 60 et 70 sont désormais triés. Le processus se poursuit jusqu'à trier tous les éléments.

Qu'est-ce que le tri par insertion

L'algorithme de tri par insertion trie l'ensemble de données en transférant un élément à la fois vers le tableau partiellement trié. Ainsi, cet algorithme de tri a un faible surcoût.

Considérez l'exemple suivant:

40 30 10 70 50 20 60

Nous considérons 40 comme le tableau partiellement trié. Quand on considère 30, c'est moins de 40. Donc on les échange. Ensuite, nous considérons que 30 et 40 sont dans le tableau partiellement trié.

30 40 10 70 50 20 60

Maintenant, nous considérons 10. 10 est inférieur à 30. Donc, nous plaçons les éléments comme ci-dessous. 10, 30 et 40 sont dans le tableau partiellement trié.

10 30 40 70 50 20 60

Maintenant, nous considérons 70. Il est supérieur à 40, il n'y a donc pas besoin de mouvement. 10, 30, 40, 70 sont dans le tableau partiellement trié.

Maintenant, considérons 50. C'est inférieur à 70 mais supérieur à 40. Nous pouvons les placer dans la bonne position. 10, 30, 40, 50, 70 sont maintenant dans le tableau partiellement trié.

10 30 40 50 70 20 60

Maintenant, considérons 20. Il est supérieur à 10 mais inférieur à 20. Nous pouvons le placer dans la bonne position. 10, 20, 30, 40, 50, 70 sont dans le tableau partiellement trié.

10 20 30 40 50 70 60

Considérez 60. Il est inférieur à 70 mais supérieur à 50. Nous pouvons le placer dans la bonne position.

10 20 30 40 50 60 70

Maintenant, nous pouvons voir que tous les éléments sont triés. Ici, le nombre d'échanges dans le tri par insertion est minimisé mais le nombre de comparaisons est toujours élevé.

Différence entre le tri à bulles et le tri par insertion

Définition

Le tri à bulles est un algorithme de tri simple qui parcourt à plusieurs reprises une liste, compare les paires adjacentes et les échange si elles sont dans le mauvais ordre. Le tri par insertion, en revanche, est un algorithme de tri simple qui construit la liste triée finale en transférant un élément à la fois. C'est donc la principale différence entre le tri à bulles et le tri par insertion.

Fonctionnalité

Alors que le tri à bulles vérifie les éléments voisins et les échange en conséquence, le tri par insertion transfère un élément à la fois vers le tableau partiellement trié.

Nombre d'échanges

De plus, le nombre d'échanges est une différence importante entre le tri à bulles et le tri par insertion. Le tri par insertion a moins de swaps par rapport au tri à bulles.

La vitesse

Complexité

Une autre différence entre le tri à bulles et le tri par insertion est que le tri par insertion est plus complexe que le tri à bulles.

Conclusion

Le tri à bulles et le tri par insertion conviennent au tri d'un petit ensemble de données. Les deux ont une efficacité inférieure par rapport à d'autres algorithmes de tri avancés tels que le tri rapide et le tri par fusion. le différence principale entre le tri à bulles et le tri par insertion est que le tri à bulles effectue le tri en vérifiant les éléments de données voisins et en les échangeant s'ils sont dans le mauvais ordre, tandis que le tri par insertion effectue le tri en transférant un élément vers le tableau partiellement trié à la fois.

Les références:

1. "Tri par bulles". Wikipédia, Wikimedia Foundation, 15 avril 2019, disponible ici. 2. « Tri par insertion ». Wikipédia, Wikimedia Foundation, 3 février 2019, disponible ici. 3. « Qu'est-ce qu'un tri par insertion ? – Définition de Techopedia. Techopedia.com, disponible ici.

Image de courtoisie:

1.1. "2816806" (CC0) via Pixabay