Tri à bulles

Le tri à bulles est un algorithme de tri par comparaison qui compare à plusieurs reprises des éléments adjacents et les échange lorsqu’ils ne sont pas dans l’ordre croissant. Après chaque passe complète, la plus grande valeur encore présente dans la partie non triée a rejoint sa position définitive, à droite. Son nom évoque ce déplacement répété dans la liste. Le tri à bulles est facile à suivre et à implémenter, mais son temps d’exécution quadratique le rend peu adapté aux grandes collections.

Algorithme du tri à bulles

Pour un tableau A contenant n éléments, comparez A[0] à A[1], puis A[1] à A[2], et poursuivez ainsi dans la partie non triée. Lorsque la valeur de gauche est supérieure à celle de droite, échangez-les. Cette condition produit un ordre croissant ; inversez la comparaison pour trier dans l’ordre décroissant.

Une passe consiste en un balayage de gauche à droite. À la fin, la plus grande valeur de la portion parcourue se trouve à sa limite droite ; la passe suivante peut donc s’arrêter une position plus tôt. La première passe porte sur n - 1 paires, la suivante sur n - 2, et ainsi de suite. Une implémentation à nombre fixe de passes en effectue n - 1, même si la dernière ne vérifie qu’une seule paire. Les listes de moins de deux éléments ne nécessitent aucune comparaison.

Exemple de tri à bulles

Considérons l’entrée (5, 3, 4, 2, 1). Lors de la première passe, comparez les paires adjacentes dans l’ordre : 5 et 3 sont échangés, ce qui donne (3, 5, 4, 2, 1) ; 5 et 4 sont échangés, ce qui donne (3, 4, 5, 2, 1) ; 5 et 2 sont échangés, ce qui donne (3, 4, 2, 5, 1) ; enfin, 5 et 1 sont échangés, ce qui donne (3, 4, 2, 1, 5). La plus grande valeur est maintenant à sa place, à droite.

La deuxième passe ne parcourt que les quatre premières valeurs et produit (3, 2, 1, 4, 5). La troisième passe transforme ce préfixe non trié en (2, 1, 3, 4, 5), puis la quatrième le transforme en (1, 2, 3, 4, 5). Cette trace montre pourquoi la limite recule après chaque passe et pourquoi les valeurs déjà placées ne sont plus comparées.

Implémentation du tri à bulles en C++

Ce programme complet trie l’exemple sur place. La limite de la boucle interne, n - i - 1, évite de comparer le suffixe déjà placé, tandis que values[j] > values[j + 1] échange une paire adjacente dans le désordre et fait avancer les valeurs les plus petites vers la gauche.

Exécutez cet exemple :

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

#include <iostream>
#include <utility>
#include <vector>

void bubble_sort(std::vector<int>& values) {
    const int n = static_cast<int>(values.size());
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (values[j] > values[j + 1]) {
                std::swap(values[j], values[j + 1]);
            }
        }
    }
}

int main() {
    std::vector<int> values{5, 3, 4, 2, 1};
    bubble_sort(values);
    std::cout << "Sorted:";
    for (int value : values) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';
}

Sorted: 1 2 3 4 5

L’exécution fournie s’est terminée avec succès et a affiché Sorted: 1 2 3 4 5. Le libellé Sorted: reste en anglais dans l’exemple ; les valeurs qui le suivent sont triées.

Complexité et limites du tri à bulles

Pour tout ordre d’entrée, l’implémentation à nombre fixe de passes effectue (n - 1) + (n - 2) + ... + 1, soit n(n - 1) / 2 comparaisons. Ses complexités temporelles dans le meilleur, le cas moyen et le pire cas sont donc toutes O(n²). Le pire cas, par exemple une entrée triée dans l’ordre inverse, nécessite également de nombreux échanges. L’implémentation modifie directement le vecteur et n’utilise qu’une valeur temporaire pour effectuer un échange ; sa complexité spatiale auxiliaire est donc O(1).

Une variante avec arrêt anticipé peut vérifier si une passe a effectué des échanges et s’arrêter lorsqu’une passe laisse la liste inchangée. Cette variante prend O(n) sur une entrée déjà triée, tandis que ses complexités dans le cas moyen et le pire cas restent O(n²). Le code à nombre fixe de passes présenté plus haut n’inclut pas cette optimisation. Le tri à bulles est utile pour apprendre les comparaisons adjacentes et pour les très petites entrées, mais les algorithmes de tri de la bibliothèque standard conviennent généralement mieux aux grandes collections.