Le tri à bulle en langage C , également connu sous le nom de tri par propagation, est l’un des algorithmes de tri les plus simples mais les moins efficaces. Il tire son nom du processus de “propagation” des éléments non triés vers la fin de la liste, à la manière de bulles d’air remontant à la surface d’un liquide. Bien qu’il ne soit pas utilisé dans des applications de production en raison de sa lenteur pour de grandes quantités de données, il est souvent enseigné comme un exemple introductif d’algorithme de tri.
Dans cet article, nous allons explorer en détail le fonctionnement du tri à bulle en langage C, en fournissant une explication étape par étape de son implémentation.
L’algorithme de tri à bulle fonctionne en parcourant répétitivement la liste à trier, en comparant chaque paire d’éléments adjacents et en les échangeant s’ils sont dans le mauvais ordre. Cette opération est répétée jusqu’à ce qu’il n’y ait plus de permutations nécessaires, ce qui signifie que la liste est triée.
Voici les étapes de base du tri à bulle :
Voici une implémentation simple du tri à bulle en langage C :
#include <stdio.h>
// Fonction de tri à bulle
void bubbleSort(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Échange les éléments
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Fonction pour afficher un tableau
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Fonction principale
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Tableau non trié : \n");
printArray(arr, n);
bubbleSort(arr, n);
printf("Tableau trié : \n");
printArray(arr, n);
return 0;
}
Dans cet exemple, nous avons une fonction bubbleSort
qui prend un tableau d’entiers et sa taille en arguments et trie le tableau en place. La fonction printArray
est utilisée pour afficher les éléments du tableau avant et après le tri.
Nous mettons en lumière ci-après quelques exemples supplémentaires d’implémentation du tri à bulle en langage C, avec des variantes et des commentaires pour expliquer chaque approche :
#include <stdio.h>
// Fonction de tri à bulle
void bubbleSort(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Échange les éléments
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Tableau non trié : \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
bubbleSort(arr, n);
printf("Tableau trié : \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
#include <stdio.h>
#include <stdbool.h>
// Fonction de tri à bulle
void bubbleSort(int arr[], int n) {
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Échange les éléments
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// Si aucun échange n'est effectué, le tableau est déjà trié
if (!swapped)
break;
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Tableau non trié : \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
bubbleSort(arr, n);
printf("Tableau trié : \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
Ces exemples illustrent différentes façons d’implémenter le tri à bulle en C, du code classique au code optimisé avec une vérification d’échange.
Voici comment les cas particuliers du tri à bulle peuvent être illustrés avec des exemples de code en langage C :
#include <stdio.h>
#include <stdbool.h>
// Fonction de tri à bulle avec optimisation pour les tableaux déjà triés
void bubbleSort(int arr[], int n) {
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Échange les éléments
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// Si aucun échange n'est effectué, le tableau est déjà trié
if (!swapped)
break;
}
}
int main() {
int arr[] = {11, 22, 25, 34, 64, 90}; // Tableau déjà trié
int n = sizeof(arr) / sizeof(arr[0]);
printf("Tableau non trié : \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
bubbleSort(arr, n);
printf("Tableau trié : \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
Dans cet exemple, le tableau arr
est déjà trié. La fonction bubbleSort
est appelée, mais elle détecte que le tableau est déjà trié grâce à la variable swapped
et sort immédiatement.
#include <stdio.h>
#include <stdbool.h>
// Fonction de tri à bulle avec optimisation pour les tableaux presque triés
void bubbleSort(int arr[], int n) {
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Échange les éléments
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// Si aucun échange n'est effectué, le tableau est déjà trié
if (!swapped)
break;
}
}
int main() {
int arr[] = {90, 64, 34, 25, 22, 11}; // Tableau inversé
int n = sizeof(arr) / sizeof(arr[0]);
printf("Tableau non trié : \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
bubbleSort(arr, n);
printf("Tableau trié : \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
Dans cet exemple, le tableau arr
est trié dans l’ordre inverse. Bien que le tri à bulle nécessite (O(n^2)) opérations dans ce cas, il est toujours capable de trier le tableau correctement.
#include <stdio.h>
// Fonction de tri à bulle pour les petits tableaux
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Échange les éléments
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11}; // Petit tableau
int n = sizeof(arr) / sizeof(arr[0]);
printf("Tableau non trié : \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
bubbleSort(arr, n);
printf("Tableau trié : \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
Dans cet exemple, le tableau arr
est petit, ce qui signifie que même si le tri à bulle est moins efficace pour de grandes quantités de données, il peut encore trier le tableau rapidement et correctement.
Ces exemples illustrent comment les cas particuliers du tri à bulle peuvent être traités dans l’implémentation en langage C.
Bien que le tri à bulle soit simple à comprendre et à mettre en œuvre, il n’est généralement pas utilisé dans des applications réelles en raison de sa lenteur pour de grandes quantités de données. Cependant, il reste un excellent moyen d’introduire les concepts fondamentaux des algorithmes de tri aux étudiants en informatique. En comprenant le fonctionnement du tri à bulle, on peut mieux appréhender des algorithmes de tri plus efficaces et complexes.
Le commentaire composé est un exercice littéraire qui consiste à analyser un texte en respectant…
Les adjectifs liés en français sont les adjectifs qui s’accordent en genre (masculin/féminin) et en…
Voici une liste étendue de mots piégeux en français, avec leurs genres et des explications…
Apprendre à distinguer le genre des noms en français peut être un véritable défi pour…
1. Informations Générales Nom complet : Charles-Louis de Secondat, Baron de La Brède et de…
Introduction L’Art de la Guerre (Dell’arte della guerra), publié en 1521, est l’un des ouvrages…
This website uses cookies.