Tri à bulles et par insertion
Tris simples
Tri à bulles et par insertion est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C Academy comprend 4 leçons au total.
Tris simples
Le tri à bulles et le tri par insertion sont les deux tris par comparaison les plus simples. Tous deux sont en O(n au carré) dans le pire des cas, mais ils sont faciles à comprendre et utiles pour les petits tableaux ou les tableaux presque triés.
Fonctionnement du tri à bulles
Le tri à bulles parcourt le tableau à plusieurs reprises en échangeant les paires adjacentes qui ne sont pas dans le bon ordre. Après chaque parcours complet, le plus grand élément restant remonte jusqu’à sa position finale à la fin du tableau.
Échanger deux entiers
Une fonction auxiliaire d’échange réutilisable permet de conserver un code de tri clair.
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a; *a = *b; *b = t;
}
int main(void) {
int x = 1, y = 2;
swap(&x, &y);
printf("%d %d\n", x, y);
return 0;
}Implémentation du tri à bulles
Boucles imbriquées : la boucle externe compte les parcours, tandis que la boucle interne compare les paires adjacentes et les échange. Après le parcours i, les i derniers éléments sont triés.
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
bubble_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Optimisation par arrêt anticipé
Si un parcours complet n’effectue aucun échange, le tableau est déjà trié et vous pouvez vous arrêter. Le tri à bulles s’exécute alors en O(n) sur une entrée déjà triée.
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = 1;
}
if (!swapped) break;
}
}
int main(void) {
int a[] = {1, 2, 3, 4, 5};
bubble_sort(a, 5);
printf("sorted with early exit\n");
return 0;
}Fonctionnement du tri par insertion
Le tri par insertion construit une zone triée au début du tableau. Pour chaque nouvel élément, il décale vers la droite les éléments triés plus grands, puis place le nouvel élément à l’endroit approprié, comme lorsque vous triez des cartes à jouer en main.
Implémentation du tri par insertion
Prenez l’élément key = a[i], puis décalez d’un emplacement vers la droite chaque élément plus grand de a[0..i-1], et insérez key dans l’espace ainsi créé.
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Tri par insertion sur des données presque triées
Le tri par insertion est particulièrement efficace lorsque le tableau est presque trié : chaque élément ne se déplace que de quelques positions, ce qui se rapproche de O(n). C’est pourquoi il est utilisé comme étape finale dans les tris hybrides.
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
}
int main(void) {
int a[] = {1, 2, 4, 3, 5}; /* one out of place */
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Stabilité
Les deux tris sont stables : les éléments égaux conservent leur ordre relatif d’origine, car ils ne sont échangés ou décalés que lors d’une comparaison strictement supérieure. La stabilité est importante lorsque vous triez des enregistrements selon plusieurs clés.
Comparaison de la complexité
Les deux algorithmes sont en O(n au carré) en moyenne comme dans le pire des cas, mais ils diffèrent en pratique :
- Tri à bulles : nombreux échanges, rarement utilisé dans du code réel
- Tri par insertion : moins d’écritures, excellent pour les petits tableaux ou les tableaux presque triés
Avec les optimisations, le meilleur cas des deux est O(n).
Compter les opérations
Comptons les comparaisons effectuées par le tri par insertion sur un tableau trié dans l’ordre inverse, qui représente le pire cas.
#include <stdio.h>
int main(void) {
int a[] = {5, 4, 3, 2, 1};
int n = 5; long cmp = 0;
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && (cmp++, a[j] > key)) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
printf("comparisons = %ld\n", cmp);
return 0;
}Vérification rapide
Testez votre compréhension des tris simples.
Récapitulatif
Vous avez appris deux tris simples en O(n au carré).
- Le tri à bulles échange les paires adjacentes à chaque parcours
- Le tri par insertion décale les éléments et les insère dans une zone triée au début
- Les deux sont stables et atteignent O(n) sur une entrée triée grâce à l’optimisation
- Le tri par insertion est le meilleur choix pratique pour les petites quantités de données
Apprends C avec un tuteur IA — gratuit
Écris et exécute du vrai code dans ton navigateur, obtiens de l'aide instantanée d'un tuteur IA disponible 24h/24, et reprends là où tu t'es arrêté sur le web ou dans l'app.
- Cours
- 39
- Leçons
- 144
Questions Fréquemment Posées
La leçon « Tri à bulles et par insertion » est-elle gratuite ?
Oui — le texte complet de « Tri à bulles et par insertion » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C Academy, passe à CoddyKit PRO. Le cours C Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Tri à bulles et par insertion » ?
Tris simples Tu pratiques C Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer C Academy ?
Aucune expérience préalable n'est requise. C Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Tri à bulles et par insertion » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon C Academy ?
Oui. Chaque leçon C Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Tri à bulles et par insertion
- Tri rapide
- Tri fusion
- Utiliser qsort