Masar — Ton parcours vers le Bac

Tri à bulles optimisé — drapeau d'échange

Idée directrice

Le tri à bulles optimisé parcourt le tableau en échangeant les paires désordonnées et s'arrête dès qu'une passe ne fait aucun échange (`Echange = faux`), ou quand il ne reste qu'un élément.

Signature de reconnaissance — l'énoncé se trahit ainsi

« PROC TRIER »

« Echange ← faux »

« T[i] > T[i+1] »

Sujet principal

Exercice — dans l'esprit des sujets d'informatique

3 questionsCorrigé masqué

On dispose d'un tableau `T[1..N]` d'entiers. On veut le trier dans l'ordre croissant par la procédure `TRIER` du corrigé bac 2015 (tri à bulles avec drapeau).

Écrire l'algorithme de `TRIER(T, N)` : boucle `Répéter`…`Jusqu'à`, drapeau `Echange`, boucle interne `Pour i de 1 à n-1`, permutation si `T[i] > T[i+1]`, puis `n ← n-1`.
Pourquoi réduit-on `n` après chaque passe ? Quel est l'effet sur le nombre de comparaisons ?
Appliquer une passe sur `T = [4, 1, 3, 2]` : donner le tableau après la première passe et la valeur de `Echange`.

Voir la correction commentéeAprès avoir posé votre démarche

1. Procédure (corrigé 2015).

```
DEF PROC TRIER (VAR T : VECT ; N : ENTIER)
Variables i, Aux, n : entier ; Echange : booléen
Début
n ← N
Répéter
Echange ← faux
Pour i de 1 à n-1 faire
Si T[i] > T[i+1] alors
Aux ← T[i] ; T[i] ← T[i+1] ; T[i+1] ← Aux
Echange ← vrai
FinSi
FinPour
n ← n-1
Jusqu'à (n = 1) ou (Echange = faux)
Fin
```

2. Après une passe, le plus grand élément restant est en position `n` : il est déjà bien placé. On exclut cet indice des prochaines comparaisons → complexité au pire toujours $O(N^2)$ , mais moins de paires testées à chaque tour.

3. Paires : (4,1)→échange [1,4,3,2] ; (4,3)→[1,3,4,2] ; (4,2)→[1,3,2,4]. `Echange = vrai`. Le tri à bulles a fait flotter le 4 en fin de tableau.

Exercices d'entraînement — une nuance à la fois

Entraînement 01 / 01

Drill TS-B.1 — Condition d'arrêt

1 questionCorrigé masqué

Dans le tri à bulles du corrigé 2015, la boucle s'arrête quand `(n=1) ou (Echange = faux)`. Interpréter chacune des deux conditions en une phrase (lien avec le tableau trié / taille restante).

Voir la correction commentéeAprès avoir posé votre démarche

`n=1` : plus qu'un élément à considérer, le tableau est nécessairement trié. `Echange = faux` : la dernière passe n'a fait aucune permutation, donc le tableau est déjà dans l'ordre croissant (optimisation du tri à bulles, corrigé 2015).

Méthode / Automatismes

Drapeau `Echange` : arrêt anticipé si le tableau est déjà trié.
Ne pas confondre avec le tri par sélection (un min par passe) ou par insertion.

Pièges classiques

Oublier de remettre `Echange ← faux` en début de passe ; boucler jusqu'à `n` au lieu de `n-1`.