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.
L’offre commerciale est un élément essentiel dans le développement de toute relation d’affaires. Bien conçue,…
Pour qu'une proposition commerciale soit percutante et engageante, elle doit être personnalisée en fonction des…
Le contexte d'une proposition commerciale professionnelle est la base qui permet d’établir la pertinence de…
Recevoir une proposition d’embauche est toujours un moment gratifiant. C’est l’aboutissement d’un processus souvent long…
10 Modèles de lettres pour Refuser Poliment une Offre Commerciale 👇 Refuser une offre commerciale…
La feuille de route produit est un document stratégique qui guide le développement, le lancement,…
This website uses cookies.