Le tri à bulles (bubble sort) en C et C++
Dans cette leçon, vous allez implémenter le tri à bulles en échangeant sans cesse les paires d'éléments voisins qui sont dans le mauvais ordre.
Introduction
Le tri à bulles parcourt le tableau plusieurs fois, compare chaque paire d'éléments voisins et les échange s'ils sont dans le mauvais ordre. À chaque passage, la plus grande valeur non encore triée se déplace progressivement vers la fin du tableau.
Points importants
- Testez avec une entrée vide, un seul élément, des doublons et des données déjà triées.
- Rendez d'abord le code correct, optimisez ensuite.
- Dans du vrai code, préférez les fonctions toutes prêtes de la bibliothèque standard.
Visualisation de Le tri à bulles (bubble sort) en C et C++
O(n)Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.
Exemples de code C et C++
#include <stdio.h>
int main(void) {
int values[] = {5, 1, 4, 2};
for (int end = 3; end > 0; --end) {
int changed = 0;
for (int index = 0; index < end; ++index) {
if (values[index] > values[index + 1]) {
int temporary = values[index];
values[index] = values[index + 1];
values[index + 1] = temporary;
changed = 1;
}
}
if (!changed) break;
}
for (int index = 0; index < 4; ++index) {
printf("%d ", values[index]);
}
}
1 2 4 5#include <iostream>
#include <vector>
int main() {
std::vector values{5, 1, 4, 2};
for (auto end = values.end(); end != values.begin(); --end) {
bool changed = false;
for (auto item = values.begin(); item + 1 != end; ++item) {
if (*item > *(item + 1)) {
std::iter_swap(item, item + 1);
changed = true;
}
}
if (!changed) break;
}
for (int value : values) {
std::cout << value << ' ';
}
}
1 2 4 5Comparaison entre C et C++
La variable changed indique s'il y a eu au moins un échange pendant le passage. S'il n'y en a eu aucun, le tableau est déjà trié et la boucle s'arrête plus tôt, un tableau déjà trié ne coûte donc que O(n). Dans le pire des cas, l'algorithme demande O(n²), c'est pourquoi il sert surtout à apprendre. En pratique, le code C++ utilise généralement std::sort.
Les boucles, les pointeurs, les longueurs et les tampons temporaires sont écrits explicitement.
Les itérateurs et les algorithmes standard séparent le traitement de la façon dont les données sont stockées.
Exercices d'approfondissement
Exécutez les deux versions, puis modifiez le code pour observer la différence de sécurité qu'apporte chaque langage.
- Déroulez chaque comparaison sur papier.
- Testez avec des doublons et des valeurs très grandes et très petites.
- Mesurez le temps d'exécution de votre code et comparez-le à la bibliothèque standard.
S'entraîner avec un défi
Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.
Tous les défis