git et de make.Implémenter les algorithmes du tri à bulles (voir ce lien) et du tri par tas (voir ce lien) pour des tableaux de nombres entiers remplis de nombres aléatoires dont la taille sera passée en argument du programme (à la ligne de commande) et mesurer les performances de chaque algorithme.
Pour chaque algorithme, la signature de la fonction de tri doit être de la forme
void sort(int32_t *sorted, const int32_t * orig,
int32_t nitems, bool (*comp)(int32_t, int32_t));afin de permettre de trier par ordre croissant ou décroissant sans changer l’implémentation de vote algorithme de tri.
Pour chacun de ces tris, écrire un programme permettant de vérifier automatiquement si le tableau final est bien trié. De plus, écrire un programme exécutant au moins 1000 tris successifs et mesurer la moyenne et l’écart-type du temps d’exécution de chaque tri pour différentes tailles de tableaux et comparer les temps moyens d’exécution entre les différents tris pour déterminer le plus efficace.
Comparez vos implémentation avec le temps d’exécution pour la
fonction qsort de la librairie
standard C (voir man 3 qsort pour plus
d’informations).
Afin de déterminer la complexité de ces tris vous pouvez afficher les
résultats sur un graphique pour des tailles de tableaux de
10, 100, 1000, 10000, 100000, 1000000.
Chaque programme devra avoir sa propre cible dans le
Makefile.
Les mesures de temps peuvent être effectuées avec la fonction
clock_gettime() de
la librairie time.h comme montré ci-dessous:
struct timespec start, finish;
clock_gettime(CLOCK_MONOTONIC, &start);
// code à mesurer
clock_gettime(CLOCK_MONOTONIC, &finish);
double seconds_elapsed = finish.tv_sec-start.tv_sec;
seconds_elapsed += (finish.tv_nsec-start.tv_nsec)/1.0e9;N’oubliez pas de ne mesurer que les fonctions de tris.