Tri par bulle vs Tri par sélection
Le tri par bulles est un algorithme de tri qui fonctionne en parcourant la liste à trier à plusieurs reprises 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'aucune autre permutation ne soit nécessaire. Le tri par 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 les éléments échangés dans l'ordre.
Qu'est-ce que le tri à bulles ?
Le tri par bulles est un algorithme de tri qui fonctionne en parcourant la liste à trier à plusieurs reprises 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. Ce parcours est répété jusqu'à ce qu'aucun échange supplémentaire ne soit nécessaire (ce qui signifie que la liste est triée). Étant donné que les plus petits éléments de la liste arrivent en haut lorsqu'une bulle apparaît à la surface, on lui donne le nom de tri par bulle. Le tri à bulles est un algorithme de tri très simple mais il a une complexité temporelle moyenne de O(n2) lors du tri d'une liste à n éléments. Pour cette raison, le tri à bulles n'est pas adapté au tri de listes contenant un grand nombre d'éléments. Mais en raison de sa simplicité, le tri à bulles est enseigné lors des introductions aux algorithmes.
Qu'est-ce que le tri par sélection ?
Le tri par 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é dans le 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 les éléments permuté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'agrandit de gauche à droite. Le tri par sélection a également une complexité temporelle moyenne de O(n2). Par conséquent, il ne convient pas non plus au tri de grandes listes.
Quelle est la différence entre le tri à bulles et le tri par sélection ?
Même si les algorithmes de tri à bulles et de tri par sélection ont des complexités temporelles moyennes de O(n2), le tri à bulles est presque toujours surpassé par le tri par sélection. Cela est dû au nombre d'échanges nécessaires aux deux algorithmes (les tris à bulles nécessitent plus d'échanges). Mais en raison de la simplicité du tri à bulles, 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 par bulles est un algorithme stable.
