Tri à bulles d'un tableau⚓︎
Principe du tri à bulles
On parcourt le tableau et on échange deux éléments consécutifs s'ils ne sont pas correctement rangés.
On démontre que si on exécute \(n-1\) parcours en appliquant le même procédé d'échange, on obtient un tableau trié.
Simplification: après le premier parcours, la plus grande valeur se trouve en dernière position. C'est sa position définitive. Au parcours suivant, il n'est donc plus nécessaire de la comparer avec l'élément précédent et on arrête les comparaisons à l'avant dernier élément. Les deux plus grands élément sont alors à leur places définitives. Au parcours suivant, le troisième, on n'effectue donc aucune comparaisons avec les deux derniers éléments. Et ainsi de suite.
Trier votre tableau
Objectifs : Écrire une fonction tri_bulles qui prend en paramètre un tableau d'entiers nombres et opère un tri en place de ce tableau en appliquant l'algorithme du tri à bulles.
- La fonction ne renvoie rien, (à part
None) ; inutile de placerreturn. - Le tableau
nombresest modifié par la fonction sans utiliser d'espace mémoire supplémentaire; on parle donc de tri en place.
Exemples
>>> nb_premiers = [2, 11, 3, 7, 5]
>>> tri_bulles(nb_premiers)
>>> nb_premiers
[2, 3, 5, 7, 11]
>>> seul = [42]
>>> tri_bulles(seul)
>>> seul
[42]
>>> vide = []
>>> tri_bulles(vide)
>>> vide
[]
Compléter le code Python ci-dessous qui implémente la fonction tri_bulles.
# Tests(insensible à la casse)(Ctrl+I)