Le tri à bulles ou Bubble Sort

Dans cet article, nous allons aborder l'algorithme du tri à bulles. Il s'agit d'un algorithme de tri simple et basique. Le principe du tri à bulles (bubble sort ou sinking sort) est de comparer deux à deux les éléments e₁ et e₂ consécutifs d'un tableau et d'effectuer une permutation si e₁ > e₂. On continue de trier jusqu'à ce qu'il n'y ait plus de permutation possible. Les comparaisons répétées font apparaître l’élément le plus grand vers la fin du tableau, d’où le nom de tri à bulles. Bien qu’il ne soit pas très efficace, il représente toujours la base des algorithmes de tri.

Fonctionnement du tri à bulles

Le tri à bulles repose sur des comparaisons et permutations répétées d'éléments adjacents jusqu'à ce qu'ils soient dans l'ordre voulu. Il est appelé tri à bulles parce que le mouvement des éléments d'un tableau ressemble au mouvement des bulles d'air dans l'eau. Dans l'eau, les bulles remontent à la surface ; de même, les éléments du tableau dans le tri à bulles se déplacent vers la fin à chaque itération.

Bien qu'il soit simple à utiliser, il est principalement utilisé comme outil pédagogique car les performances du tri à bulles sont faibles dans le monde réel. Il n'est pas adapté aux grands ensembles de données. La complexité moyenne et la complexité dans le pire des cas du tri à bulles est de O(n^2), où n est le nombre d'éléments du tableau.

Le tri à bulles est principalement utilisé lorsque :

• la complexité n'a pas d'importance
• un code simple et court est préféré

Algorithme du tri à bulles

PROCEDURE tri_bulle ( TABLEAU a[1:n])
passage ← 0
REPETER
    permut ← FAUX
    POUR i VARIANT DE 1 A n - 1 - passage FAIRE
        SI a[i] > a[i+1] ALORS
            permuter a[i] ET a[i+1]
            permut ← VRAI
        FIN SI
    FIN POUR
    passage ← passage + 1
TANT QUE permut = VRAI

 Exemple d’algorithme de tri à bulles

Supposons que nous ayons le tableau suivant : [74, 57, 69, 41, 9, 17]. Nous allons le trier en utilisant l’algorithme de tri à bulles.

Initialisez passage = 0.

Premier passage :

permut = FAUX ; passage = 0

permut = VRAI ; passage = 1

Deuxième passage :

permut = FAUX ; passage = 1

permut = VRAI ; passage = 2

Troisième passage :

permut = FAUX ; passage = 2

permut = VRAI ; passage = 3

Quatrième passage :

permut = FAUX ; passage = 3

permut = VRAI ; passage = 4

Cinquième passage :

permut = FAUX ; passage = 4

permut = FAUX ; passage = 5

L'algorithme se termine après le cinquième passage et le tableau trié est : [9, 17, 41, 57, 69, 74]. Il faut noter qu'après le quatrième passage, le tableau est déjà trié mais permut = VRAI, ce qui explique pourquoi l'algorithme continue de s'exécuter.

Complexité de l'algorithme du tri à bulles

1. Complexité temporelle

• Complexité dans le meilleur cas : Elle se produit lorsqu'aucun tri n'est nécessaire, c'est-à-dire que le tableau est déjà trié. Dans le meilleur des cas, seules n comparaisons sont nécessaires. La complexité temporelle du tri à bulles est donc de O(n).
• Complexité dans le cas moyen : Elle se produit lorsque les éléments du tableau sont mélangés dans un ordre qui n'est ni ascendant ni descendant. En moyenne n-i comparaisons sont faites à chaque passage. Donc, s’il y a n passages, alors la complexité temporelle moyenne peut être exprimée par : (n-1) + (n-2) + (n-3) ..... + 1 = n*(n-1)/2. La complexité moyenne du tri à bulles est donc de O(n^2).
• Complexité dans le pire cas : Le cas le plus défavorable se produit lorsque les éléments du tableau doivent être triés dans l'ordre inverse. Cela signifie que vous devez trier les éléments du tableau dans l'ordre croissant, mais que ces éléments sont dans l'ordre décroissant. Dans le pire des cas, la complexité temporelle du tri à bulles est de O(n^2).

2. Complexité spatiale

La complexité spatiale du tri à bulles est de O(1), car une variable supplémentaire est nécessaire pour la permutation.

Implémentation de l'algorithme du tri à bulles

Le code ci-dessous est une implémentation de l'algorithme du tri à bulles en langage C.

#include <stdio.h>

typedef int bool;
enum { false, true };

void bubbleSort(int* tableau, int n) {
    int passage = 0;
    bool permutation = true;
    int i;
   
    while ( permutation) {
        permutation = false;
        passage ++;
        for (i=0; i<n-passage; i++) {
            if (tableau[i]>tableau[i+1]){
                permutation = true;
                // on permute les deux éléments
                int temp = tableau[i];
                tableau[i] = tableau[i+1];
                tableau[i+1] = temp;
            }
        }
    }
}

// fonction pour afficher les éléments du tableau
void printArr(int a[], int n) {  
	for (int i = 0; i < n; ++i)  
		printf("%d \t", a[i]);
	printf("\n");
} 

int main() {  
	//int tab[] = {74, 35, 103, 57, 69, 41, 9, 17, 3};
	int tab[] = {74, 57, 69, 41, 9, 17};  
	int n = sizeof(tab) / sizeof(tab[0]); // n est la taille du tableau

	printf("Contenu du tableau avant le tri :\n");  
	printArr(tab, n);  
	bubbleSort(tab, n);  
	printf("\nContenu du tableau après le tri :\n");  
	printArr(tab, n);  
}

Résultat :

L'exécution du code précédent produit le résultat ci-dessous :

Contenu du tableau avant le tri :
74 	57 	69 	41 	9 	17 	

Contenu du tableau après le tri :
9 	17 	41 	57 	69 	74