ProjetsSystèmes, réseau & algorithmes
CPP Module 09
Tri de Ford-Johnson et visualiseur
- Période
- sept. 2025 – oct. 2025
- Cadre
- cursus 42
- Équipe
- solo
- Note
- 100/100 · outstanding ×3
- C++
- Algorithmes
- Programmation orientée objet
- Mathématiques
- Testeur
Le dernier module de la piscine C++, autour des conteneurs de la STL. Son dernier exercice demande d’implémenter le tri de Ford-Johnson, un algorithme qui cherche à trier en faisant le moins de comparaisons possible.
Les exercices
Trois exercices, trois conteneurs : un convertisseur de cours du bitcoin qui cherche la date la plus proche dans une std::map, une calculatrice en notation polonaise inverse sur une pile, et le tri de Ford-Johnson, appliqué à deux conteneurs différents pour comparer leurs performances.
Ford-Johnson
On range les nombres par paires, et on compare chaque paire : le plus grand va dans la « chaîne principale », le plus petit attend. La chaîne principale est triée récursivement avec le même algorithme. Ensuite, chaque petit élément est inséré par recherche dichotomique.
L’astuce est dans l’ordre d’insertion : les nombres de Jacobsthal (1, 3, 5, 11, 21…) désignent des groupes à insérer de la fin vers le début. Chaque recherche se fait alors sur une zone dont la taille est juste sous une puissance de deux, ce qui économise des comparaisons.
Le visualiseur
Pour m’amuser, j’ai ajouté un visualiseur dans le terminal, en C++23 avec la bibliothèque FTXUI : il lance le programme avec différents paramètres et affiche les résultats, pour voir comment se comportent les deux conteneurs selon la taille des données.
Ce que j’en retiens
- Un algorithme peut être optimal en comparaisons sans être le plus rapide en pratique.
- Le choix du conteneur pèse autant que l’algorithme.