Présentation de l'exercice

L'exercice du tri à bulles est l'un des classiques proposés sur la plateforme France IOI. Il s'agit d'implémenter un algorithme de tri simple, puis souvent d'en analyser la complexité ou de compter le nombre d'échanges effectués.

Dans cet article, nous détaillons la correction pas à pas, en expliquant chaque étape de la logique pour que vous compreniez pourquoi le code fonctionne, et pas seulement comment.

Énoncé typique

On vous demande de trier un tableau de N entiers en utilisant le tri à bulles, puis d'afficher le tableau trié ainsi que le nombre total d'échanges réalisés.

Analyse du problème

Le tri à bulles compare deux éléments adjacents et les échange si nécessaire. En répétant ce processus, les valeurs les plus grandes « remontent » progressivement vers la fin du tableau, comme des bulles.

  • Complexité temporelle : O(n²) dans le pire cas
  • Complexité spatiale : O(1) — tri en place
  • Stabilité : Oui, le tri à bulles est stable

Solution en Python


n = int(input())
tableau = list(map(int, input().split()))

echanges = 0
for i in range(n):
    for j in range(0, n - i - 1):
        if tableau[j] > tableau[j + 1]:
            tableau[j], tableau[j + 1] = tableau[j + 1], tableau[j]
            echanges += 1

print(" ".join(map(str, tableau)))
print("Nombre d'échanges :", echanges)

Explication ligne par ligne

  1. Lecture des entrées : On lit d'abord la taille du tableau, puis les valeurs sur une seconde ligne.
  2. Double boucle : La boucle externe i représente le nombre de passes. Après chaque passe, le plus grand élément non trié est placé à sa position finale.
  3. Comparaison adjacente : La boucle interne compare tableau[j] et tableau[j+1]. Si le premier est plus grand, on les échange.
  4. Comptage : On incrémente echanges à chaque fois qu'un échange a lieu.

Solution en C++


#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int tab[n];
    for (int i = 0; i < n; i++) cin >> tab[i];

    int echanges = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (tab[j] > tab[j+1]) {
                swap(tab[j], tab[j+1]);
                echanges++;
            }
        }
    }

    for (int i = 0; i < n; i++) cout << tab[i] << " ";
    cout << endl << "Echanges : " << echanges << endl;
    return 0;
}

Optimisation possible

Une optimisation classique consiste à ajouter un indicateur booléen permutation. Si aucun échange n'a lieu lors d'une passe, le tableau est déjà trié et on peut arrêter prématurément :


for i in range(n):
    permutation = False
    for j in range(0, n - i - 1):
        if tableau[j] > tableau[j + 1]:
            tableau[j], tableau[j + 1] = tableau[j + 1], tableau[j]
            permutation = True
    if not permutation:
        break

Erreurs fréquentes à éviter

  • Oublier de réduire la borne de la boucle interne (n - i - 1) — sans ça, on refait des comparaisons inutiles.
  • Confondre tri à bulles et tri par sélection : dans le tri par sélection, on cherche le minimum à chaque passe.
  • Ne pas lire correctement le format d'entrée (séparateur espace vs retour à la ligne).

Conclusion

Le tri à bulles est un excellent point de départ pour comprendre les algorithmes de tri. Même si peu efficace sur de grands jeux de données, il illustre parfaitement les notions de comparaison, d'échange et de complexité algorithmique — des bases indispensables pour progresser sur France IOI.