Tri à bulles
Dernière mise à jour
Le tri à bulles parcourt la liste de façon répétée, compare chaque paire d'éléments adjacents et les échange s'ils sont dans le mauvais ordre. Après chaque passe complète, la plus grande valeur restante a « remonté » comme une bulle jusqu'à sa position correcte à la fin, si bien que chaque passe examine un élément de moins. Appuyez sur lecture ci-dessus pour observer les comparaisons et les échanges, ou avancez pas à pas.
C'est l'un des algorithmes de tri les plus simples à comprendre, ce qui en fait un excellent premier algorithme, mais son temps d'exécution O(n²) le rend impraticable pour de grandes entrées.
Complexité temporelle et spatiale
| Cas | Complexité | Remarques |
|---|---|---|
| Meilleur cas | O(n) | Déjà trié, avec une vérification de sortie anticipée |
| Cas moyen | O(n²) | Ordre aléatoire |
| Pire cas | O(n²) | Trié à l'envers |
| Espace | O(1) | En place, seulement une variable temporaire |
| Stable | Oui | Les éléments égaux conservent leur ordre relatif |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | Commencez au début du tableau. |
| 2 | Comparez l'élément courant avec le suivant. |
| 3 | S'ils sont dans le mauvais ordre, échangez-les. |
| 4 | Avancez d'une position vers la droite et répétez jusqu'à la fin (une passe). |
| 5 | Répétez les passes ; chaque passe fixe un élément de plus à la fin. |
| 6 | Arrêtez quand une passe complète ne fait aucun échange. |
Exemple résolu
Tri de [5, 2, 4, 1] :
| Passe | Tableau | Action |
|---|---|---|
| 1 | [2, 4, 1, 5] | Échange 5,2, puis 5,4, puis 5,1 ; le 5 remonte jusqu'à la fin. |
| 2 | [2, 1, 4, 5] | 2,4 dans l'ordre ; échange 4,1 ; 4,5 dans l'ordre ; le 4 est placé. |
| 3 | [1, 2, 4, 5] | Échange 2,1 ; le reste est déjà dans l'ordre ; le 2 est placé. |
| 4 | [1, 2, 4, 5] | Une passe complète ne fait aucun échange, donc le tableau est trié et l'algorithme s'arrête. |
Quand utiliser le tri à bulles
| Utilisez-le quand | Évitez-le quand |
|---|---|
| Vous enseignez ou apprenez le fonctionnement des tris par comparaison | Vous triez de grandes entrées, où O(n²) est bien trop lent |
L'entrée est minuscule ou presque triée (avec sortie anticipée, il s'approche de O(n)) | Vous avez besoin du tri généraliste le plus rapide - utilisez quicksort ou merge sort |
| Vous voulez un tri stable, en place, avec quasiment aucun code | Les données sont dans un ordre aléatoire et la performance compte |
| Vous détectez si une liste courte est déjà triée en une seule passe | Les écritures nombreuses sont coûteuses (ex. mémoire flash) ; le tri par sélection fait moins d'échanges |
Code de Bubble Sort
Une implémentation propre et exécutable de Bubble Sort en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Bubble Sort en Python
Python
1def bubble_sort(a):2 n = len(a)3 for i in range(n - 1):4 swapped = False5 for j in range(n - 1 - i):6 if a[j] > a[j + 1]:7 a[j], a[j + 1] = a[j + 1], a[j]8 swapped = True9 if not swapped:10 break # no swaps means the list is already sorted11 return a12
13
14nums = [5, 1, 4, 2, 8]15print("Before:", nums)16bubble_sort(nums)17print("After: ", nums)Code de Bubble Sort en JavaScript
JavaScript
1function bubbleSort(a) {2 for (let end = a.length - 1; end > 0; end--) {3 let swapped = false;4 for (let j = 0; j < end; j++) {5 if (a[j] > a[j + 1]) {6 [a[j], a[j + 1]] = [a[j + 1], a[j]];7 swapped = true;8 }9 }10 if (!swapped) break; // Already sorted: stop early11 }12 return a;13}14
15const data = [5, 2, 9, 1, 7, 3];16console.log("Before:", data);17console.log("Sorted:", bubbleSort([...data]));Code de Bubble Sort en Java
Java
1import java.util.Arrays;2
3public class Main {4 static void bubbleSort(int[] arr) {5 for (int i = arr.length - 1; i > 0; i--) {6 boolean swapped = false;7 for (int j = 0; j < i; j++) {8 if (arr[j] > arr[j + 1]) {9 int tmp = arr[j];10 arr[j] = arr[j + 1];11 arr[j + 1] = tmp;12 swapped = true;13 }14 }15 if (!swapped) break; // already sorted16 }17 }18
19 public static void main(String[] args) {20 int[] arr = {5, 1, 4, 2, 8, 3};21 System.out.println("Before: " + Arrays.toString(arr));22 bubbleSort(arr);23 System.out.println("After: " + Arrays.toString(arr));24 }25}Code de Bubble Sort en C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void bubbleSort(std::vector<int>& a) {11 for (size_t pass = 0; pass + 1 < a.size(); ++pass) {12 bool swapped = false;13 // Each pass bubbles the largest remaining value to the end14 for (size_t j = 0; j + 1 < a.size() - pass; ++j) {15 if (a[j] > a[j + 1]) {16 std::swap(a[j], a[j + 1]);17 swapped = true;18 }19 }20 if (!swapped) break; // already sorted21 }22}23
24int main() {25 std::vector<int> data = {5, 1, 4, 2, 8, 3};26 std::cout << "Before: ";27 printVec(data);28 bubbleSort(data);29 std::cout << "After: ";30 printVec(data);31 return 0;32}Code de Bubble Sort en C
C
1#include <stdbool.h>2#include <stdio.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9void bubbleSort(int a[], int n) {10 for (int pass = 0; pass < n - 1; pass++) {11 bool swapped = false;12 // Each pass bubbles the largest remaining value to the end13 for (int j = 0; j < n - 1 - pass; j++) {14 if (a[j] > a[j + 1]) {15 int tmp = a[j];16 a[j] = a[j + 1];17 a[j + 1] = tmp;18 swapped = true;19 }20 }21 if (!swapped) break; // already sorted22 }23}24
25int main(void) {26 int data[] = {5, 1, 4, 2, 8, 3};27 int n = sizeof(data) / sizeof(data[0]);28 printf("Before: ");29 printArr(data, n);30 bubbleSort(data, n);31 printf("After: ");32 printArr(data, n);33 return 0;34}FAQ sur le tri à bulles
Quelle est la complexité temporelle du tri à bulles ?
Le tri à bulles s'exécute en temps
O(n²) dans les cas moyen et pire à cause des boucles imbriquées. Avec une optimisation de sortie anticipée, il peut atteindre O(n) sur un tableau déjà trié. Il utilise O(1) d'espace supplémentaire.Le tri à bulles est-il stable ?
Oui. Le tri à bulles n'échange les éléments adjacents que lorsqu'ils sont strictement dans le mauvais ordre, si bien que les éléments égaux ne se dépassent jamais et conservent leur ordre relatif d'origine.
Pourquoi l'appelle-t-on tri à bulles ?
À chaque passe, la plus grande valeur non triée se déplace pas à pas vers la fin du tableau, comme une bulle qui remonte à la surface - d'où le nom « tri à bulles ».
Quelle est la différence entre le tri à bulles et le tri par insertion ?
Les deux s'exécutent en
O(n²), sont stables et en place, mais déplacent les données différemment : le tri à bulles échange de façon répétée les paires adjacentes mal ordonnées, tandis que le tri par insertion prend chaque élément et le glisse à sa bonne place dans le préfixe trié. Le tri par insertion effectue généralement moins d'écritures et est plus rapide en pratique, surtout sur des données presque triées.Quand devrais-je utiliser le tri à bulles plutôt que quicksort ?
Presque jamais pour des charges réelles - le temps moyen
O(n log n) de quicksort écrase le O(n²) du tri à bulles sur tout sauf des entrées minuscules. Le tri à bulles ne vaut la peine que lorsque la liste est très petite ou presque triée, ou quand vous voulez le tri stable le plus simple possible pour enseigner.L'optimisation de sortie anticipée change-t-elle le pire cas du tri à bulles ?
Non. Suivre si une passe a effectué un échange permet au tri à bulles de s'arrêter tôt et d'atteindre
O(n) sur une entrée déjà triée, mais un tableau trié à l'envers nécessite toujours toutes les comparaisons, donc le pire cas reste O(n²). L'optimisation n'aide que le meilleur cas et les cas presque triés.Ressources associées
Plus de visualisations
