Une autre différence considérable entre les deux réside dans le fait que le tri à bulle est un algorithme stable, tandis que le tri par sélection est un algorithme instable. Un algorithme est considéré comme stable, les éléments avec la même clé apparaissant dans le même ordre que lors de leur tri dans la liste ou le tableau. Généralement, la plupart des algorithmes stables et rapides utilisent de la mémoire supplémentaire.
Tableau de comparaison
| Base de comparaison | Sorte de bulle | Tri de sélection |
|---|---|---|
| De base | L'élément adjacent est comparé et échangé | L'élément le plus grand est sélectionné et échangé avec le dernier élément (en cas d'ordre croissant). |
| Meilleure complexité du temps de traitement | Sur) | O (n 2 ) |
| Efficacité | Inefficace | Efficacité améliorée par rapport au tri en bulle |
| Stable | Oui | Non |
| Méthode | Échanger | Sélection |
| La vitesse | Lent | Rapide par rapport au type à bulle |
Définition du tri à bulles
Le tri à bulles est l'algorithme itératif le plus simple. Il consiste à comparer chaque élément ou élément avec l'élément à côté de celui-ci et à les permuter si nécessaire. En termes simples, il compare les premier et deuxième éléments de la liste et les échange sauf s’ils ne sont pas dans un ordre spécifique. De même, les deuxième et troisième éléments sont comparés et échangés, et cette comparaison et cet échange se terminent à la fin de la liste. Le nombre de comparaisons dans la première itération est n-1, n étant le nombre d'éléments dans un tableau. L'élément le plus important serait à la nième position après la première itération. Et après chaque itération, le nombre de comparaisons diminue et finalement, une seule comparaison est effectuée.
Cet algorithme est l'algorithme de tri le plus lent. La meilleure complexité de cas (lorsque la liste est en ordre) du type Bubble est de l'ordre n ( O (n) ), et dans le pire des cas, la complexité est O (n2) . Dans le meilleur des cas, il est d'ordre n car il compare simplement les éléments sans les échanger. Cette technique nécessite également un espace supplémentaire pour stocker la variable temporaire.
Définition du tri par sélection
Le tri par sélection a obtenu des performances légèrement meilleures et est plus efficace que l’algorithme de tri à bulle. Supposons que nous voulions organiser un tableau dans l'ordre croissant, puis il fonctionne en recherchant le plus grand élément et en l'échangant avec le dernier élément. Répétez le processus suivant sur les sous-tableaux jusqu'à ce que toute la liste soit triée.
Principales différences entre le tri par bulle et le tri par sélection
- Dans le type à bulle, chaque élément et son élément adjacent sont comparés et échangés si nécessaire. D'autre part, le tri par sélection fonctionne en sélectionnant l'élément et en permutant cet élément particulier avec le dernier élément. L'élément sélectionné peut être le plus grand ou le plus petit en fonction de l'ordre, c'est-à-dire croissant ou décroissant.
- La complexité la plus défavorable est la même dans les deux algorithmes, c’est-à-dire, O (n2), mais la complexité optimale est différente. Le tri à bulles prend un ordre de n fois tandis que le tri à la sélection consomme un temps de n2.
- Le tri à bulles est un algorithme stable, en revanche, le tri à sélection est instable.
- L'algorithme de tri de sélection est rapide et efficace par rapport au tri à bulle qui est très lent et inefficace.
Conclusion
L'algorithme de tri à bulles est considéré comme l'algorithme le plus simple et le plus inefficace, mais l'algorithme de tri à la sélection est efficace par rapport au tri à bulles. Le tri à bulles consomme également de l'espace supplémentaire pour stocker la variable temporaire et nécessite davantage de swaps.
