Différence entre le tri des bulles et le tri de sélection

Toi de bulles vs tri de sélection

Bubble Sort est un algorithme de tri qui fonctionne en parcourant la liste pour être triés à plusieurs reprises tout en comparant des paires d'éléments qui sont adjacents. Si une paire d'éléments est dans le mauvais ordre, ils sont échangés pour les placer dans le bon ordre. Cette traversée est répétée jusqu'à ce qu'aucun autre échange ne soit requis. Le tri de sélection est également un algorithme de tri, qui commence par trouver l'élément minimum dans la liste et l'échanger 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.

Qu'est-ce que le tri des bulles?

Bubble Sort est un algorithme de tri qui fonctionne en parcourant la liste pour être triés à plusieurs reprises tout en comparant des paires d'éléments qui sont adjacents. Si une paire d'éléments est dans le mauvais ordre, ils sont échangés pour les placer dans le bon ordre. Cette traversée est répétée jusqu'à ce qu'aucun autre échange ne soit requis (ce qui signifie que la liste est triée). Étant donné que les petits éléments de la liste arrivent au sommet alors qu'une bulle revient à la surface, il reçoit le type de bulle de nom. Le tri à bulles est un algorithme de tri très simple, mais il a une complexité de temps de cas moyenne de O (n2) lors du tri d'une liste avec n éléments. Pour cette raison, le tri des bulles ne convient pas pour le tri des listes avec un grand nombre d'éléments. Mais à cause de sa simplicité, le tri de bulles est enseigné lors des introductions aux algorithmes.

Qu'est-ce que le tri de sélection?

Le tri de sélection est également un autre algorithme de tri qui commence par trouver l'élément minimum dans la liste et l'échanger avec le premier élément. Ensuite, l'élément minimum est trouvé à partir du reste de la liste (du deuxième élément jusqu'au dernier élément de la liste) et échangé avec le deuxième é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. Donc, dans le tri de sélection, à n'importe quelle étape de l'algorithme, la liste est divisée en deux parties où une partie contient des éléments triés et l'autre partie contient des éléments non triés. Au fur et à mesure que l'algorithme se déroule, la liste triée passe de gauche à droite. Le tri de sélection a également une complexité de temps de cas moyenne de O (N2). Par conséquent, il ne convient pas non plus pour trier les grandes listes.

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

Même si les algorithmes de tri à bulles et de tri de sélection ont des complexités de temps de cas moyen de O (N2), le tri des bulles est presque tous les temps surclassé par le tri de sélection. Cela est dû au nombre de swaps nécessaires aux deux algorithmes (les tri à bulles ont besoin de plus d'échanges). Mais en raison de la simplicité du tri des bulles, sa taille de code est très petite. La stabilité est une autre différence dans 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 avec une valeur égale. En ce sens, le tri de sélection n'est pas un algorithme stable tandis que le tri des bulles est un algorithme stable.