Tri à bulles

PerformanceEdit

Le tri par bulles a une complexité moyenne et dans le pire des cas de О (n2), où n est le nombre déléments triés. La plupart des algorithmes de tri pratiques ont une complexité nettement meilleure dans le pire des cas ou dans la moyenne, souvent O (n log n). Même dautres algorithmes de tri О (n2), tels que le tri par insertion, fonctionnent généralement plus rapidement que le tri à bulles et ne sont pas plus complexes. Par conséquent, le tri par bulles nest pas un algorithme de tri pratique.

Le seul avantage significatif du tri par bulles par rapport à la plupart des autres algorithmes, même le tri rapide, mais pas le tri par insertion, est que la capacité de détecter que la liste est triée efficacement est intégré à lalgorithme. Lorsque la liste est déjà triée (dans le meilleur des cas), la complexité du tri à bulles nest que de O (n). En revanche, la plupart des autres algorithmes, même ceux avec une meilleure complexité moyenne des cas, effectuent tout leur processus de tri sur lensemble et sont donc plus complexes. Cependant, non seulement le tri par insertion partage cet avantage, mais il fonctionne également mieux sur une liste qui est sensiblement triée (ayant un petit nombre dinversions). De plus, si ce comportement est souhaité, il peut être ajouté de manière triviale à tout autre algorithme en vérifiant la liste avant lexécution de lalgorithme.

Le tri par bulles doit être évité dans le cas de grandes collections. Cela ne sera pas efficace dans le cas dune collection inversée.

Rabbits and TurtlesEdit

La distance et la direction que les éléments doivent déplacer pendant le tri déterminent les performances du tri à bulles car les éléments se déplacent dans des directions différentes à des vitesses différentes. Un élément qui doit se déplacer vers la fin de la liste peut se déplacer rapidement car il peut participer à des échanges successifs. Par exemple, le plus grand élément de la liste remportera chaque échange, il passe donc à sa position triée lors de la première passe, même si elle commence près du début. En revanche, un élément qui doit se déplacer vers le début de la liste ne peut pas se déplacer plus rapidement quune étape par passe, les éléments se déplacent donc très lentement vers le début. Si le plus petit élément se trouve à la fin de la liste, il faudra n − 1 passes pour le déplacer vers le début. Cela a conduit à ce que ces types d’éléments soient appelés lapins et tortues, respectivement, d’après les personnages de la fable dEsope de La tortue et le lièvre.

Divers des efforts ont été faits pour éliminer les tortues afin daméliorer la vitesse de tri des bulles. Le type de cocktail est un type de bulle bidirectionnel qui va du début à la fin, puis sinverse, allant de bout en début. Il peut assez bien déplacer les tortues, mais il conserve la complexité du pire des cas O (n2). Le tri en peigne compare les éléments séparés par de grands espaces et peut déplacer les tortues extrêmement rapidement avant de passer à des espaces de plus en plus petits pour lisser la liste. Sa vitesse moyenne est comparable à des algorithmes plus rapides comme le tri rapide.

Exemple étape par étapeModifier

Prenez un tableau de nombres « 5 1 4 2 8 » et triez le tableau du plus bas nombre au plus grand nombre en utilisant le tri à bulles. À chaque étape, les éléments écrits en gras sont comparés. Trois passes seront nécessaires;

First Pass (5 1 4 2 8) → (1 5 4 2 8), Ici, lalgorithme compare les deux premiers éléments, et échange depuis 5 > 1. (1 5 4 2 8) → (1 4 5 2 8), Swap depuis 5 > 4 (1 4 5 2 8) → (1 4 2 5 8), Swap depuis 5 > 2 (1 4 2 5 8) → (1 4 2 5 8), Maintenant, puisque ces éléments sont déjà dans lordre (8 > 5), lalgorithme ne les échange pas. Deuxième passe (1 4 2 5 8) → (1 4 2 5 8) (1 4 2 5 8) → (1 2 4 5 8), Swap depuis 4 > 2 ( 1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8)

Maintenant, le tableau est déjà trié, mais lalgorithme ne sait pas sil est terminé . Lalgorithme a besoin dune passe entière sans aucun échange pour savoir quil est trié.