tpcpp04.md

TP C++ n°4

Tri d'un tableau de caractères

Le tri est un problème classique qui permet d'étudier à la fois la correction algorithmique et les performances.

Objectif

Implémenter plusieurs algorithmes de tri et analyser leurs comportements sur des jeux de données comparables.

Notions C++

• tableaux et parcours indexés ;
• fonctions et modularisation ;
• tris à bulles, sélection, insertion, rapide ;
• instrumentation simple (compteurs de comparaisons/manipulations).

Pré-requis

• TP n°3 ;
• boucles imbriquées ;
• fonctions.

Travail demandé

Écrire un programme qui trie un tableau de caractères (ou de codes caractères) selon différents algorithmes, puis compare les résultats et coûts observés.

1. Implémentations

Implémenter :

• tri à bulles, ;
• tri par sélection, ;
• tri par insertion, ;
• tri rapide.

2. Vérification

Vérifier que chaque méthode produit le même tableau trié final.

3. Mesure

Compter les comparaisons/manipulations (ou mesurer le temps) pour chaque tri.

4. Analyse

Comparer les comportements selon la distribution des données.

Contraintes techniques

• Compilateur GNU C++ ;
• Système d'exploitation Linux, Mac OS X ou Ms-Windows ;
• Standard recommandé : C++11 ou supérieur.

Exemples d'entrée/sortie

Exemple de jeu d'entrée : D B A C

Sortie attendue (quel que soit l'algorithme) : A B C D

Compilation

g++ -std=c++11 -Wall -Wextra -o test_tri test_tri.cxx tri.cxx

Livrables

• tri.h ;
• tri.cxx ;
• test_tri.cxx ;
• README.md (protocole de comparaison + résultats).

Extensions possibles (bonus)

• Ajouter une version avec std::vector<int> ;
• Ajouter une comparaison avec std::sort.

Critères d'évaluation

• Correction des algorithmes ;
• Robustesse des bornes et des cas limites ;
• Qualité de l'analyse comparative ;
• Qualité des tests et du README.