🫧 Tri à Bulles Optimisé : Cours & Principes

📖 1. Définition

Le tri à bulles optimisé utilise une variable booléenne (drapeau) nommée echange pour détecter si des permutations ont eu lieu au cours d’une passe. Si aucune permutation n’est effectuée, cela signifie que le tableau est déjà entièrement trié, ce qui permet d’arrêter prématurément l’algorithme.

⚙️ 2. Principe de l’algorithme

Le fonctionnement repose sur les étapes clés suivantes :

  • Initialiser le drapeau echange ← Faux au début de chaque passe.
  • Parcourir le tableau pour comparer les éléments adjacents T[i] et T[i+1].
  • En cas de désordre, échanger les éléments et positionner echange ← Vrai.
  • Réduire la zone de parcours à chaque fin de passe (n ← n - 1) et répéter tant que echange est Vrai.

⚠️ Note très importante :

L’utilisation de la fonction prédéfinie en Python .sort() ou sorted() est strictement hors programme. Vous devez obligatoirement implémenter la logique itérative avec le drapeau d’échange.

📊 Simulation Visuelle & Algorithme Animé

Visualisez pas à pas les comparaisons adjacentes, les échanges et l’état du tableau.

📊 Espace de simulation

450ms
🤖 i

Suivi de l’exécution (i, echange) :

i Générez ou lancez la simulation… i
echange – echange

État du tableau T après chaque passe :

Passe Valeurs du tableau T (éléments permutés en évidence)
Initial –

Algorithme & TDOL :

Procédure Tri_Bulles(@T: Tab, n: Entier)
Début
    Répéter
        echange ← Faux
        Pour i de 0 à n-2 Faire
            Si T[i] > T[i+1] Alors
                tmp ← T[i]
                T[i] ← T[i+1]
                T[i+1] ← tmp
                echange ← Vrai
            FinSi
        FinPour
        n ← n - 1
    Jusqu'à Non echange
Fin

TDOL

Objet Type
i, tmp Entier
echange Booléen

💻 Traduction en Python

def tri_bulles(T, n):
    echange = True
    while echange:
        echange = False
        for i in range(0, n - 1):
            if T[i] > T[i + 1]:
                tmp = T[i]
                T[i] = T[i + 1]
                T[i + 1] = tmp
                echange = True
        n -= 1

📝 3. Exercice d’application

Situation : Dans un tournoi de jeux vidéo, les scores finaux des participants sont saisis dans un tableau. Pour afficher le classement officiel du plus petit au plus grand score de manière optimisée, l’organisateur applique l’algorithme du tri à bulles avec un drapeau d’échange.

Écrire un programme modulaire permettant de :

  • Saisir le nombre de participants N (compris entre 2 et 50).
  • Remplir le tableau avec leurs scores.
  • Trier les scores par ordre croissant à l’aide de la procédure du tri à bulles optimisé.
  • Afficher le tableau des scores triés.

Donner la solution sous forme d’algorithme et sa traduction en programme Python.

Correction détaillée

💻 Programme Principal (Algorithme)

Algorithme Classement_Scores_Tournoi
DEBUT
  SaisieTaille(N)
  RemplirTableau(Scores, N)
  TriBulles(Scores, N)
  AfficherTableau(Scores, N)
FIN

📋 Tableaux de Déclaration (TDNT & TDOG)

TDNT

Type Structure
Tab Tableau de 50 entiers

TDOG (avec les noms des procédures)

Objet Type / Nature
Scores Tab
N Entier
SaisieTaille Procédure
RemplirTableau Procédure
TriBulles Procédure
AfficherTableau Procédure

⚙️ Liste des Modules (Procédures) et TDOL

1. Procédure SaisieTaille

Procedure SaisieTaille(@n: Entier)
DEBUT
  Répéter
    Ecrire("Donner le nombre de participants (entre 2 et 50) : ")
    Lire(n)
  Jusqu'à n dans [2..50]
FIN

TDOL : Aucun objet local.

2. Procédure RemplirTableau

Procedure RemplirTableau(@t: Tab, n: Entier)
DEBUT
  Pour i de 0 à n-1 Faire
    Ecrire("Score du participant ", i+1, " : ")
    Lire(t[i])
  Fin Pour
FIN

TDOL : i (Entier)

3. Procédure TriBulles (Optimisée)

Procedure TriBulles(@t: Tab, n: Entier)
DEBUT
  Répéter
    echange ← Faux
    Pour i de 0 à n-2 Faire
      Si t[i] > t[i+1] Alors
        tmp ← t[i]
        t[i] ← t[i+1]
        t[i+1] ← tmp
        echange ← Vrai
      FinSi
    Fin Pour
    n ← n - 1
  Jusqu'à Non echange
FIN

TDOL : i, tmp (Entiers), echange (Booléen)

4. Procédure AfficherTableau

Procedure AfficherTableau(t: Tab, n: Entier)
DEBUT
  Ecrire("Classement officiel des scores :")
  Pour i de 0 à n-1 Faire
    Ecrire(t[i])
  Fin Pour
FIN

TDOL : i (Entier)

🐍 Version Python (Traduction complète)

def saisie_taille():
    n = int(input("Nombre de participants (2-50) : "))
    while not (2 <= n <= 50):
        n = int(input("Erreur (2-50) : "))
    return n

def remplir_tableau(n):
    return [int(input(f"Score participant {i+1} : ")) for i in range(n)]

def tri_bulles(t, n):
    echange = True
    while echange:
        echange = False
        for i in range(n - 1):
            if t[i] > t[i + 1]:
                tmp = t[i]
                t[i] = t[i + 1]
                t[i + 1] = tmp
                echange = True
        n -= 1

def afficher_tableau(t):
    print("Classement officiel des scores :", t)

# Programme Principal
N = saisie_taille()
Scores = remplir_tableau(N)
tri_bulles(Scores, N)
afficher_tableau(Scores)