Tri à bulles
Trier en comparant les voisins et en les échangeant, passe après passe : la plus grande valeur remonte, la borne de la boucle intérieure se réduit, et une passe sans échange permet de s'arrêter.
- 26 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Tri à bulles : de quoi s'agit-il ?
Voir la réponse
Tri qui parcourt le tableau en comparant chaque case à sa voisine de droite, les échange si elles sont dans le mauvais ordre, et recommence.
À la fin de la passe 1, le plus grand élément est tout à droite ; à la fin de la passe 2, le deuxième plus grand est à sa place, et ainsi de suite.
Qu'affiche ce programme ? Il fait une seule passe du tri à bulles.
```python
t = [4, 1, 3, 2]
for j in range(len(t) - 1):
if t[j] > t[j + 1]:
t[j], t[j + 1] = t[j + 1], t[j]
print(t)`[1, 3, 2, 4][1, 2, 3, 4][1, 4, 3, 2][1, 3, 4, 2]
Voir la réponse
[1, 3, 2, 4]Le 4 est échangé avec le 1, puis avec le 3, puis avec le 2 : il est emporté jusqu'au bout. Le 3 et le 2 n'ont jamais été comparés entre eux, il reste donc un désordre pour la passe suivante.
Après la passe 1 du tri à bulles, c'est le … élément qui est à sa place définitive, tout à … du tableau.
Voir la réponse
Après la passe 1 du tri à bulles, c'est le plus grand élément qui est à sa place définitive, tout à droite du tableau.
Un grand élément est emporté de case en case à chaque comparaison, jusqu'à en rencontrer un plus grand. Le plus grand de tous va donc jusqu'au bout.
Arrêt anticipé : de quoi s'agit-il ?
Voir la réponse
Amélioration qui interrompt le tri dès qu'une passe complète n'a effectué aucun échange, signe que le tableau est trié.
Elle repose sur un drapeau remis à
Falseau début de chaque passe et mis àTrueà chaque échange. Sur un tableau trié, une seule passe suffit.