Masar — Les scénarios du Bac, reliés à ton travail

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 une procédure TRIER (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.

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 ce tri à bulles, 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.