Différence entre le tri par bulle et le tri par sélection

Tri à bulles vs Tri de sélection

Le tri à bulles est un algorithme de tri qui consiste à parcourir la liste pour trier de manière répétée tout en comparant des paires d'éléments adjacents. Si une paire d'éléments est dans le mauvais ordre, ils sont permutés pour les placer dans le bon ordre. Cette traversée est répétée jusqu'à ce qu'aucun échange supplémentaire ne soit nécessaire. Le tri par sélection est également un algorithme de tri, qui commence par rechercher l'élément minimum dans la liste et en l'échangeant avec le premier élément. Ce processus est répété pour le reste de la liste en plaçant des éléments échangés dans l'ordre.

Quel est le type de bulle?

Le tri à bulles est un algorithme de tri qui consiste à parcourir la liste pour trier de manière répétée tout en comparant des paires d'éléments adjacents. Si une paire d'éléments est dans le mauvais ordre, ils sont permutés pour les placer dans le bon ordre. Cette traversée est répétée jusqu'à ce qu'aucun échange supplémentaire ne soit nécessaire (ce qui signifie que la liste est triée). Étant donné que les éléments les plus petits de la liste arrivent en haut à la surface, une bulle s’apparente à la surface. Le tri à bulles est un algorithme de tri très simple, mais il a une complexité de temps de cas moyen de O (n2) lors du tri d'une liste avec n éléments. De ce fait, le tri en bulle n’est pas adapté au tri des listes comportant un grand nombre d’éléments. Mais en raison de sa simplicité, le tri à bulles est enseigné lors de l'introduction d'algorithmes.

Quel est le tri par sélection?

Le tri par sélection est également un autre algorithme de tri qui commence par rechercher l'élément minimum dans la liste et en l'échangeant avec le premier élément. Ensuite, l'élément minimum est trouvé dans le reste de la liste (du deuxième élément au dernier élément de la liste) et est échangé avec le deuxième élément. Ce processus est répété pour le reste de la liste en plaçant les éléments échangés dans l'ordre. Ainsi, dans le tri par sélection, à n'importe quelle étape de l'algorithme, la liste est divisée en deux parties, une partie contenant des éléments triés et l'autre partie contenant des éléments non triés. Au fur et à mesure que l'algorithme progresse, la liste triée s'allonge de gauche à droite. Le tri de sélection a également une complexité de temps moyen de O (n2). Par conséquent, il ne convient pas non plus au tri des grandes listes.

Quelle est la différence entre le tri à bulles et le tri à la sélection?

Même si les algorithmes de tri par bulle et de tri par sélection ont des complexités de temps de cas moyen de O (n2), le tri par bulle est presque tout le temps dépassé par le tri par sélection. Cela est dû au nombre de swaps requis par les deux algorithmes (les types de bulles nécessitent davantage de swaps). Mais en raison de la simplicité du tri à bulle, la taille de son code est très petite. La stabilité est une autre différence entre ces deux algorithmes. Un algorithme de tri stable est un algorithme de tri qui conserve l'ordre des enregistrements si la liste contient des éléments de valeur égale. En ce sens, le tri par sélection n'est pas un algorithme stable alors que le tri à bulle est un algorithme stable.