Tri à bulles
Parcourt la liste encore et encore et échange les voisins qui ne sont pas dans le bon ordre. Après chaque passage, la plus grande valeur restante est à la fin.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- oui
- oui
Meilleur cas : comment le temps grandit avec la taille n de la liste quand l'entrée est la plus facile pour cet algorithme.
Cas moyen : le temps habituel selon n. En n², deux fois plus de valeurs prennent quatre fois plus de temps ; n log n croît bien moins vite.
Pire cas : la croissance sur l'entrée la plus difficile. Utile quand la vitesse ne doit jamais chuter.
Espace : la mémoire supplémentaire nécessaire en plus de la liste. 1 veut dire quelques variables, n une copie de la liste.
Stable : deux valeurs égales gardent leur ordre d'origine. Important quand on trie des fiches selon un seul champ.
En place : trie à l'intérieur de la liste elle-même, sans deuxième liste.
- comparaison
- déplacement
- à sa place finale
Essayez : Choisissez une liste presque triée. Après un passage sans échange, l'algorithme s'arrête plus tôt.
Comment ça marche
Il compare deux voisins à la fois et les échange si celui de gauche est plus grand. À chaque passage, la plus grande valeur avance donc jusqu'au bout à droite, comme une bulle qui remonte. Si un passage ne fait aucun échange, la liste est déjà triée.
Quand le choisir
Presque jamais dans de vrais programmes, car il est lent sur les longues listes. Pour apprendre, il est idéal : il montre l'idée de base du tri, comparer puis échanger. Il n'est rapide que si la liste est déjà triée.