le tri à bulle en langage C : Guide détaillé
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.
Fonctionnement de l’algorithme
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 :
- Parcourir la liste non triée.
- Comparer chaque élément avec son voisin immédiat.
- Si un élément est plus grand que son voisin, les échanger.
- Répéter les étapes 1 à 3 jusqu’à ce que plus aucun échange ne soit nécessaire.
Implémentation en langage C
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.
💡 Exemples
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 :
Tri à bulle classique :
#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;
}Tri à bulle optimisé avec un drapeau d’échange :
#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.
Exploration détaillée du tri à bulle en langage C : Cas particuliers, Optimisations et Exemples de Code
Voici comment les cas particuliers du tri à bulle peuvent être illustrés avec des exemples de code en langage C :
Cas des tableaux déjà triés
#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.
Cas des tableaux inversés
#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.
Cas des tableaux de petites tailles
#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.
Synthèse 😉
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.
1. Comment fonctionne le tri à bulle en langage C ?
- Il compare et échange les éléments adjacents jusqu’à ce que le tableau soit trié.
2. Quels sont les cas particuliers du tri à bulle ?
- Tableaux déjà triés, inversés, ou de petites tailles.
3. Quelle est l’efficacité du tri à bulle pour de grandes quantités de données ?
- Moins efficace comparé à d’autres algorithmes, comme le tri rapide ou fusion.
4. Comment optimiser le tri à bulle pour les tableaux presque triés ?
- En ajoutant une vérification pour détecter les tableaux déjà triés.
5. Le tri à bulle peut-il trier des tableaux de types de données personnalisés ?
- Oui, en définissant une fonction de comparaison appropriée.
6. Est-il possible de paralléliser le tri à bulle pour améliorer les performances ?
- Oui, avec des outils comme OpenMP pour exploiter les ressources multicœurs.
7. Le tri à bulle est-il adapté pour les petits tableaux ?
- Oui, sa simplicité le rend approprié pour les petites quantités de données.
8. Comment détecter si un tableau est déjà trié avant d’appliquer le tri à bulle ?
- En ajoutant une vérification à chaque itération pour détecter les échanges.
9. Quelle est la complexité temporelle du tri à bulle ?
- Dans le pire cas, O(n^2), dans le meilleur cas, O(n).
10. Le tri à bulle peut-il trier des tableaux de données de différents types ?
- Oui, en utilisant des pointeurs de fonction pour les comparaisons personnalisées.
Autres articles
