Aller au menu - Aller au contenu

Icône Le tri à bulles

Par Avatar shareman
Mise à jour : 08/10/2008
Creative Commons BY-SA
557 visites depuis 7 jours , classé 197/777
Bonjour les zér0s !

Quel est le premier algorithme de tri auquel on pense intuitivement lors de nos premiers pas dans le monde du tri? On a tendance à comparer deux à deux les éléments d'un tableau ou d'une liste à trier et d'échanger leur position s'ils sont mal placés. Et bien, ce tri porte un nom : c'est le tri à bulles.

Dans son cours sur le langage C, et plus particulièrement dans le chapitre sur les tableaux, m@teo21 donne pour exercice (n°5) l'élaboration d'une méthode (d'un algorithme) pour trier un tableau. On se rend compte que la plupart des zér0s implémentent (peut-être sans le savoir) le tri à bulles. En réalité, un débutant a 99% de chances de l'implémenter dans ses débuts en algorithmique.

L'algorithme est original (mais malheureusement lent) et je vais vous le présenter ici.
Retour en haut
Sommaire du tutoriel :
Icône du chapitre
Retour en haut

Principe du tri

Le principe de l'algorithme du tri à bulles est très simple à assimiler. Il est, et de loin, l'un des algorithmes de tri les plus simples qui soient.

Pour vous expliquer le principe, je vais d'abord vous donner une courte explication écrite puis nous allons concrètement trier une liste de nombres.

Le principe du tri à bulles est de comparer deux valeurs adjacentes et d'inverser leur position si elles sont mal placées. Alors, qu'entend-t-on par "mal placé" ? C'est très simple et surtout, c'est logique : si un premier nombre x est plus grand qu'un deuxième nombre y et que l'on souhaite trier l'ensemble par ordre croissant, alors x et y sont mal placés et il faut les inverser. Si, au contraire, x est plus petit que y, alors on ne fait rien et l'on compare y à z, l'élément suivant. C'est donc itératif. Et on parcourt ainsi la liste jusqu'à ce qu'on ait réalisé n-1 passages (n représentant le nombre de valeurs à trier) ou jusqu'à ce qu'il n'y ait plus rien à inverser lors du dernier passage.

Avec de la logique, on s'aperçoit qu'au premier passage, on place le plus grand élément de la liste au bout du tableau, au bon emplacement. Pour le passage suivant, nous ne sommes donc plus obligés de faire une comparaison avec le dernière élément ; et c'est bien plus avantageux ainsi. Donc à chaque passage, le nombre de valeurs à comparer diminue de 1.

Pour illustrer ce principe, prenons la suite de nombres suivante :
Code : Autre - liste à trier
1

6 0 3 5 1 4 2

Nous voulons trier ces valeurs par ordre croissant. Commençons par le commencement. Nous allons faire un premier passage.
Code : Autre - liste à trier
1
2
3
4
5
6
7

6 0 3 5 1 4 2   // On compare 6 et 0 : on inverse
0 6 3 5 1 4 2   // On compare 6 et 3 : on inverse
0 3 6 5 1 4 2   // On compare 6 et 5 : on inverse
0 3 5 6 1 4 2   // On compare 6 et 1 : on inverse
0 3 5 1 6 4 2   // On compare 6 et 4 : on inverse
0 3 5 1 4 6 2   // On compare 6 et 2 : on inverse
0 3 5 1 4 2 6   // Nous avons terminé notre premier passage

La question à se poser est la suivante : Devons-nous continuer ? Oui car lors du dernier passage, au moins un échange a été effectué.
Nous allons donc refaire un passage mais en omettant la dernière case.
Code : Autre - liste à trier
1
2
3
4
5
6

0 3 5 1 4 2 6   // On compare 0 et 3 : on laisse
0 3 5 1 4 2 6   // On compare 3 et 5 : on laisse
0 3 5 1 4 2 6   // On compare 5 et 1 : on inverse
0 3 1 5 4 2 6   // On compare 5 et 4 : on inverse
0 3 1 4 5 2 6   // On compare 5 et 2 : on inverse
0 3 1 4 2 5 6   // Nous avons terminé notre passage

Comme promis, on ne compare pas 5 et 6 car c'est inutile et ce qui est inutile est à éviter, d'autant plus que cela ralenti l'algorithme.
Je suppose que vous avez bien compris le principe alors ce que je vous propose maintenant, c'est juste de vous montrer les dernières étapes avant d'aboutir à la liste triée.
Code : Autre - liste à trier
1
2
3
4
5

0 3 1 4 2 5 6   // On compare 0 et 3 : On laisse
0 3 1 4 2 5 6   // On compare 3 et 1 : On inverse
0 1 3 4 2 5 6   // On compare 3 et 4 : On laisse
0 1 3 4 2 5 6   // On compare 4 et 2 : On inverse
0 1 3 2 4 5 6   // Nous avons terminé notre passage

Code : Autre - liste à trier
1
2
3
4

0 1 3 2 4 5 6   // On compare 0 et 1 : On laisse
0 1 3 2 4 5 6   // On compare 1 et 3 : On laisse
0 1 3 2 4 5 6   // On compare 3 et 2 : On inverse
0 1 2 3 4 5 6   // Nous avons terminé notre passage

Code : Autre - liste à trier
1
2
3

0 1 2 3 4 5 6   // On compare 0 et 1 : On laisse
0 1 2 3 4 5 6   // On compare 1 et 2 : On laisse
0 1 2 3 4 5 6   // Nous avons terminé notre passage

À ce moment-là, l'algorithme s'arrête car il n'y a plus eu d'échange lors du dernier passage et nous retrouvons notre liste belle et bien triée !
Retour en haut

Implémentation

Dans cette sous-partie, je vais vous montrer une manière d'implémenter le tri à bulles dans un langage de programmation.

Choix du langage


En premier lieu, j'avais souhaité vous présenter une implémentation du tri à bulles en Ti-basic mais apparemment, c'était un mauvais choix. Il est vrai que tout le monde ne comprend pas ce langage (son apprentissage au lycée est facultatif) et le Ti-basic ne s'indente pas, par conséquent les différents blocs d'instructions sont plus difficilement repérables. J'ai donc rectifié cette sous-partie et j'ai choisi le langage C++, bien plus connu des Zér0s. Même si vous ne programmez pas en ce langage, vous pourrez aisément comprendre le code et ainsi le traduire.

l'algorithme


Je vais procéder de la manière suivante : Je vais vous donner le code puis je vais l'expliquer.
Code : C++ - Algorithme du tri à bulles
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
void tri_bulles(vector<int>& tab)
{
    bool tab_en_ordre = false;
    int taille = tab.size();
    while(!tab_en_ordre)
    {
        tab_en_ordre = true;
        for(int i=0 ; i < taille-1 ; i++)
        {
            if(tab[i] > tab[i+1])
            {
                swap(tab[i],tab[i+1]);
                tab_en_ordre = false;
            }
        }
        taille--;
    }
}

Intéressons nous déjà à la première ligne (void tri_bulles(vector<int>& tab) ), la fonction est de type void et prend en paramètre l'adresse d'un vector (STL) via une référence.
Passons à la suite :
Code : C++ - déclaration des variables
1
2
bool tab_en_ordre = false;
int taille = tab.size();

Voilà les seules variables dont nous aurons besoin, mis à part la variable de boucle. Le booléen tab_en_ordre permet de tester si au moins un échange a été réalisé lors du dernier passage. C'est cette variable qui va faire tourner la boucle de l'algorithme et qui permettra d'en sortir une fois le tableau trié. Pour la seconde variable, taille , elle stocke au départ la taille du vector mais nous en avons besoin car nous allons devoir la modifier à chaque passage du tableau (souvenez-vous du -1 à chaque passage).
A présent, analysons rapidement la fin du code :
Code : C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
while(!tab_en_ordre)
{
    tab_en_ordre = true;
    for(int i=0 ; i < taille-1 ; i++)
    {
        if(tab[i] > tab[i+1])
        {
            swap(tab[i],tab[i+1]);
            tab_en_ordre = false;
        }
    }
    taille--;
}

Il s'agit là concrètement de la boucle de l'algorithme du tri à bulles. Le while permet de réitérer les passages sur le tableau tant qu'au moins un échange a été effectué lors du dernier passage ; cette condition est testée avec tab_en_ordre comme dit précédemment. La boucle interne for est la boucle qui compare deux à deux les valeurs adjacentes du tableau. Si deux éléments sont mal placés, alors on entre dans le if et on les inverse grâce à std::swap .
Retour en haut

Complexité

Le tri à bulles est l'un des tris les plus lents, si ce n'est le plus lent. C'est pour cette raison que son utilisation se fait très rare et cet algorithme reste très critiqué. Mais pourquoi est-il si lent ? On évalue la rapidité d'un algorithme de tri en observant son nombre de comparaisons/échanges et on établi ainsi une échelle que l'on nomme la complexité. Le tri à bulles fait énormément de comparaisons/échanges pour peu de valeurs à trier. On estime mathématiquement qu'il fait en moyenne n(n-1)/4 opérations pour n valeurs à trier.

Avec la notation de Landau, on néglige le -1 et le /4 pour conserver l'opération n² qui croît beaucoup plus vite. C'est une croissance quadratique. En ajoutant quelques valeurs supplémentaires à trier, le rapidité de l'algorithme peut donc terriblement chuter. La complexité moyenne du tri à bulles est donc en O(n²) ce qui est extrêmement lent par rapport aux algorithmes de tri en O(n*log2(n)) tel le tri fusion.

Dans le pire des cas, la complexité du tri à bulles est aussi en O(n²). Le pire des cas est, pour ce tri, une liste triée en sens inverse. Le meilleur des cas est une liste triée. Si l'algorithme est confronté à ce cas, sa complexité s'améliore en O(n), ce qui signifie qu'il ne fait que n comparaisons pour n valeurs à trier (en réalité, pour des raisons d'intervalles, il n'en fait que n-1).

Conclusion


Le tri à bulles est l'un des plus mauvais tris en raison de sa forte complexité qui entraîne un temps d'exécution trop long. Et pourtant, cette méthode de tri ne cesse d'être utilisée et ce, sûrement, pour son originalité. Mais il faut tout de même savoir qu'elle est relativement suffisante pour des listes de petites tailles sur un ordinateur, je dis bien relativement. À partir de vingt éléments, il est déjà préférable d'utiliser un autre tri plus adapté. Il faut choisir son algorithme en fonction de ses besoins. Peut-être, un jour, aurez-vous besoin du tri à bulles.
Retour en haut

En savoir plus

Ce tutoriel vous a intéressé ? Alors n'hésitez pas à lire cette sous-partie qui fait office d'annexe.

Le tri à bulles bidirectionnel


L'une des variantes les plus connues du tri à bulles est sans doute le tri bidirectionnel ou tri Boustrophedon. D'après Wikipédia, "on qualifie de boustrophédon le tracé d'un système d'écriture qui change alternativement de sens ligne après ligne, à la manière du bœuf marquant les sillons dans les champs, de droite à gauche puis de gauche à droite". Le principe du tri à bulles bidirectionnel est justement de parcourir la liste à trier dans un sens puis dans l'autre donc en alternant le sens de passage à chaque tour. Cette technique augmente légèrement la rapidité de l'algorithme car certains éléments de la liste à trier se trouvent encore dans le buffer lors d'un passage, mais la complexité reste en O(n²).
Voici une implémentation possible du tri à bulles bidirectionnel en C++ que j'ai réalisée :
Code : C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void gauche(vector<int>&,int,int);

void droite(vector<int>& tab, int deb, int fin)
{
    bool tab_en_ordre = true;
    for(int i = deb ; i < fin ; i++)
    {
        if(tab[i] > tab[i+1])
        {
            swap(tab[i],tab[i+1]);
            tab_en_ordre = false;
        }
    }
    if(!tab_en_ordre)
    {
        gauche(tab, deb, fin-1);
    }
}
void gauche(vector<int>& tab, int deb, int fin)
{
    bool tab_en_ordre = true;
    for(int i = fin ; i > deb ; i--)
    {
        if(tab[i] < tab[i-1])
        {
            swap(tab[i],tab[i-1]);
            tab_en_ordre = false;
        }
    }
    if(!tab_en_ordre)
    {
        droite(tab, deb+1, fin);
    }
}
void tri_bulles(vector<int>& tab){
droite(tab, 0, tab.size()-1);}

Il y a certainement de meilleures implémentations mais celle-ci est ici à titre d'exemple.
Note : Cette implémentation utilise la récursivité croisée : "droite" appelle "gauche", "gauche" appelle "droite".

Liens externes


Si le tri à bulles vous intéresse, voici des liens toujours utiles :

Évidement, vous avez toutes les chances de tomber sur des sites intéressants en tapant "tri bulles" ici.
Retour en haut
J'espère que ce chapitre vous aura appris des choses sur le monde du tri.
Je vous remercie bien cordialement de m'avoir lu,

bonne continuation et bon tri !

Si vous rencontrez une difficulté quelconque, vous pouvez toujours m'envoyer un MP.
Retour en haut

Partager

Retour en haut
16 commentaires pour "Le tri à bulles"
Note moyenne : 3.88 / 4 (8 votes)
Pseudo Commentaire
Hors ligne owolaby001 # Posté le 23/07/2009 à 19:55:35

merci
Hors ligne raphamil # Posté le 24/08/2009 à 12:27:45
Avatar

Études : Université de Bordeaux

 Je trouve que tes codes pourraient être un peu plus "C++", en utilisant les itérateurs de la STL (et en plus on est indépendant du type de conteneur) :

Code : C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
template<class Iterator>void Bulle(Iterator first, Iterator last) {
    /*
    bool trie = false;
    while(!trie) {
        Iterator it = first;
        trie = true;
        while(++it != last) {
            if(*(it - 1) > *it) {
                trie = false;
                std::swap(*(it - 1), *it);
            }
        }
    }
    */
    for(Iterator it = first; it != last; ++it) {
        if(*it > *(it + 1)) {
            std::swap(*(it + 1), *it);
            it = first - 1;
        }
    }
}


La deuxième partie provoque une boucle infinie, je ne comprends pas bien pourquoi :/

Utilisation :

Code : C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iomanip>

static const size_t g_TAILLE = 8000;


int RandomNumber() {
    return rand() % g_TAILLE + 1;
}
void Randomize(std::vector<int>& i) {
    std::generate(i.begin(), i.end(), RandomNumber);
}

float Chrono(clock_t start, clock_t end) {
    return (static_cast<double>(end) - start) / CLOCKS_PER_SEC;
}

inline void TicTac() {
    static clock_t start;
    static bool tic = true;
    if(!(tic = !tic)) {
        start = clock();
    } else {
        clock_t end = clock();
        cout << std::setprecision(40) << Chrono(start, end) << 's' << std::endl;
    }
}

int main() {
    std::vector<int>tab(g_TAILLE);
    srand(time(NULL));

    Randomize(tab); TicTac();
    Bulle(tab.begin(), tab.end()); TicTac();
    //
    Randomize(tab); TicTac();
    std::sort(tab.begin(), tab.end()); TicTac();
    
    //cout << std::endl;
    return 0;
}
Les langages fonctionnels sont un rien spéciaux, mais ils changent votre manière de voir un programme. Si vous ne connaissez que des dérivés du C (PHP, Python, etc.), changez votre manière de voir ici, et avec OCaml, Haskell, ou Scheme.
 
Hors ligne shareman # Posté le 30/08/2009 à 20:51:49
ἄλφα ✞
Avatar

 Citation : raphamil
Je trouve que tes codes pourraient être un peu plus "C++"

Il ne faut pas perdre de vue une chose : j'ai écrit les codes de ce tutoriel pour qu'un débutant en C puisse les comprendre (parce que ce seront principalement eux qui liront ces codes et qui vont chercher à les comprendre, et il n'est pas rare de voir un débutant essayer d'implémenter un tri bulles sur le forum C) tout en restant dans mon langage de prédilection qui est le C++. Si j'avais voulu faire "plus C++" comme tu dis, j'aurais effectivement utilisé les iterator, qui permettent un puissant polymorphisme paramétrique (c'est le but).

Citation : raphamil
Code : C++
1
2
3
4
5
6
for(Iterator it = first; it != last; ++it) {
        if(*it > *(it + 1)) {
            std::swap(*(it + 1), *it);
            it = first - 1;
        }
    }


Cette implémentation n'est pas bonne pour au moins trois raisons :
- "last" pointe par définition "après la séquence", donc à la dernière itération de ta boucle for, ça va coincer au moment de faire *(it+1), donc au moment où le programme va chercher à déréférencer last ;
- Le "plus"- ainsi que le "moins" binaire ne sont pas des opérateurs supportés par tous les iterators, par exemple pas par ceux de std::list. Donc en écrivant it+1 ou first-1, tu casses une partie du polymorphisme qu'offrent les iterators ;
- Ton implémentation est en O(n^3) au pire des cas.
Da BHM
"Merci pour ton histoire, tu gagnes un paquet de Kleenex™." - iPoulet.
 
Hors ligne sidarape # Posté le 12/02/2010 à 19:42:26
Voici votre E.P.P.Z monsieur!
Avatar

Ville : Québec, qc
Pays : Canada
Études : Cégep Sainte-Foy

 Citation : Dutiona
Code : C++
1
2
3
4
5
6
7
8
for(int i = 0 ; i < taille-1 ; i++){
  if(tab[i] > tab[i+1]){
    temp = tab[i];
    tab[i] = tab[i+1];
    tab[i+1] = temp;
    i = -1;
  }
}

Légèrement moins performant étant donné que tu parcours tous le tableau à chaque fois au lieu de le réduire comme dans les tutoriel.
Image utilisateur

Vive le Québec Libre!!!
 
Connecté SylafrsOne # Posté le 30/06/2011 à 18:38:07
perror() could save your life
Avatar

Ville : Brunoy
Pays : France métropolitaine
Études : IUT Orsay

 Pourquoi ne pas l'avoir mis ici : Algorithmes divers multi-langage plutot ? (c'est toi le PO en plus ^^').
(Ou ne pas avoir fait de pub sur ce topic, à mon avis peu visité, par les débutants ? ^^')
__________________________________

Peut-être pouvons nous "retranscrire" ce topic (pour les tris) en big-tuto ?
ça peut-être lourd, mais faisable en pas trop de temps si on s'y met à plusieurs ^^
Image utilisateur
Image utilisateur

ce n'est jamais un bug : c'est une petite erreur.
Exercices pour les débutants [C]
 

Voir tous les commentaires