TS-BAlgorithmes de tri

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.

Ce qui aide à reconnaître la démarche

« PROC TRIER »

« Echange ← faux »

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

Besoin d’un point de départ ? Voir la méthode

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.

Les pièges à vérifier dans ta démarche

Oublier de remettre Echange ← faux en début de passe ; boucler jusqu'à n au lieu de n-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.

Changer d’énoncé, garder le raisonnement

Choisis un seul transfert après le sujet principal. Qu’est-ce qui change ? Quel résultat ou quelle méthode peux-tu réutiliser ? Les autres exercices restent disponibles pour une prochaine séance.

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

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

Entraînement 01 / 02

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).

2 Transfert — tri à bulles avec drapeau sur deux tableaux parallèles : l'échange suit les deux, et l'on compte les passes

Entraînement 02 / 02

Transfert — tri à bulles avec drapeau sur deux tableaux parallèles : l'échange suit les deux, et l'on compte les passes

4 questionsCorrigé masquéEn cours de relecture

Deux tableaux parallèles décrivent N candidats ( $2 \leq N \leq 30$ ) : Noms[1..N] (chaînes) et Notes[1..N] (réels), Noms[i] et Notes[i] concernant le même candidat. On veut afficher le classement par notes décroissantes en conservant la correspondance nom–note, à l'aide du tri à bulles avec drapeau d'échange.

Exemple : Noms = [A, B, C, D, E] et Notes = [12, 15, 9, 15, 18].

Un élève trie Notes seul avec la procédure de tri à bulles habituelle puis affiche Noms[i] et Notes[i] côte à côte. Montrer sur l'exemple, après une seule passe, pourquoi le classement affiché est faux.
Écrire l'algorithme de la procédure TrierDesc(var Noms, var Notes ; N) : tri à bulles décroissant avec drapeau Echange, chaque permutation portant sur les deux tableaux, la partie déjà en place n'étant plus parcourue. Donner son TDOL.
Donner la trace complète sur l'exemple : contenu des deux tableaux et valeur de Echange après chaque passe, puis le nombre de passes. Les deux candidats notés 15 gardent-ils leur ordre initial ? Justifier par la comparaison utilisée.
Quel est le nombre de passes pour un tableau déjà classé par notes décroissantes ? Pour un tableau classé en ordre croissant ? Quel rôle joue précisément le drapeau dans chacun de ces deux cas ? Traduire enfin TrierDesc en Python et vérifier ces deux cas ainsi que l'exemple.

Cet exercice et sa correction sont en cours de relecture. Tu peux les consulter ; l’exercice n’est pas encore proposé en séance.

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

1. Idée : deux tableaux parallèles ne restent parallèles que si chaque échange est fait dans les deux.

Une passe de tri à bulles décroissant sur Notes seul échange 12 et 15, puis 9 et 15, puis 9 et 18 : Notes = [15, 12, 15, 18, 9] alors que Noms reste [A, B, C, D, E]. L'affichage attribue 15 à A (qui a 12), 12 à B (qui a 15), 18 à D (qui a 15) : les notes ont bougé, les noms non, la correspondance est détruite dès la première passe. Toute permutation de Notes[i] et Notes[i+1] doit s'accompagner de la permutation de Noms[i] et Noms[i+1].

2. Idée : la comparaison Notes[i] < Notes[i+1] fait remonter la plus grande note ; le drapeau arrête le tri dès qu'une passe ne change rien.

0) DEF PROC TrierDesc (var Noms : TabNoms ; var Notes : TabNotes ; N : entier)
1) n ← N
2) Répéter
     Echange ← faux
     Pour i de 1 à n - 1 faire
        Si Notes[i] < Notes[i+1] alors
           auxR ← Notes[i] ; Notes[i] ← Notes[i+1] ; Notes[i+1] ← auxR
           auxC ← Noms[i]  ; Noms[i]  ← Noms[i+1]  ; Noms[i+1]  ← auxC
           Echange ← vrai
        FinSi
     FinPour
     n ← n - 1
   Jusqu'à (Echange = faux) ou (n = 1)
3) Fin TrierDesc

TDOL

Objet	Type / Nature	Rôle
n	entier	taille de la partie encore à trier
i	entier	indice de parcours de la passe
Echange	booléen	drapeau : vrai si la passe a fait au moins une permutation
auxR	réel	auxiliaire pour permuter deux notes
auxC	chaîne	auxiliaire pour permuter deux noms

La procédure suppose N déjà contrôlé à la saisie (Répéter Lire(N) Jusqu'à (N dans [2..30])) : elle ne re-vérifie pas la borne. Après chaque passe, la plus grande note de la partie parcourue est arrivée en position n : il est inutile de la comparer de nouveau, d'où n ← n - 1.

3. Idée : suivre les deux tableaux ensemble à chaque passe.

Passe	`Notes`	`Noms`	`Echange`
début	12, 15, 9, 15, 18	A, B, C, D, E	—
1 (n=5)	15, 12, 15, 18, 9	B, A, D, E, C	vrai
2 (n=4)	15, 15, 18, 12, 9	B, D, E, A, C	vrai
3 (n=3)	15, 18, 15, 12, 9	B, E, D, A, C	vrai
4 (n=2)	18, 15, 15, 12, 9	E, B, D, A, C	vrai

Après la passe 4, n vaut 1 : arrêt. Le tri a demandé $\boxed{4\text{ passes}}$ et le classement final est E (18), B (15), D (15), A (12), C (9). Les deux candidats à 15 apparaissent dans l'ordre B puis D, comme au départ : la comparaison stricte Notes[i] < Notes[i+1] n'échange pas deux notes égales (à la passe 3, 15 < 15 est faux), donc le tri à bulles ainsi écrit conserve l'ordre initial des ex æquo. Avec ≤ à la place de <, B et D auraient été permutés inutilement.

4. Idée : le drapeau ne sert que dans le meilleur cas ; dans le pire cas c'est n = 1 qui arrête.

Tableau déjà classé par notes décroissantes : la première passe ne fait aucune permutation, Echange reste faux, la boucle s'arrête après

\boxed{1\text{ passe}}

(N - 1 comparaisons seulement). Tableau classé en ordre croissant, le pire cas : chaque passe fait remonter d'une case la note en trop, il faut

\boxed{N - 1\text{ passes}}

; Echange vaut vrai à chaque passe et c'est la condition n = 1 qui arrête. Sur l'exemple (

N = 5

) le tri a coûté 4 passes, autant que le pire cas, parce que le 18 partait de la dernière position. Le drapeau est donc une optimisation du meilleur cas et des cas presque triés, sans effet sur le pire cas.

def trier_desc(noms, notes):
    n = len(notes)
    passes = 0
    if n <= 1:
        return passes
    while True:
        echange = False
        passes += 1
        for i in range(n - 1):
            if notes[i] < notes[i + 1]:
                notes[i], notes[i + 1] = notes[i + 1], notes[i]
                noms[i], noms[i + 1] = noms[i + 1], noms[i]
                echange = True
        n -= 1
        if n == 1 or not echange:
            return passes

print(trier_desc(list("ABCDE"), [12, 15, 9, 15, 18])) affiche 4 et laisse [E, B, D, A, C] / [18, 15, 15, 12, 9] ; trier_desc(list("ABC"), [20, 10, 5]) retourne 1 sans rien changer ; trier_desc(list("ABCDE"), [1, 2, 3, 4, 5]) retourne 4 et renverse les deux tableaux. Le test n <= 1 protège le cas d'un seul candidat, où il n'y a rien à trier.

Relier ce raisonnement au bac

Choisis une filière pour voir les sujets qui étayent ce scénario.

Tu écris. Tu continues.

Où veux-tu aller ?

Tri à bulles optimisé — drapeau d'échange

Exercice — dans l'esprit des sujets d'informatique

Changer d’énoncé, garder le raisonnement

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

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

Transfert — tri à bulles avec drapeau sur deux tableaux parallèles : l'échange suit les deux, et l'on compte les passes

Relier ce raisonnement au bac