Buts

• Introduction à la compilation séparée
• Introduction à make
• Création de librairies
• Réusinage
• Mesure de complexité

Énoncé

Reprendre le travail pratique des tris (voir l’énoncé suivant), ajouter l’implémentation du bubble sort (ou tri à bulles), et l’implémentation récursive du merge sort (ou tri à fusion). Pour chaque tri, créer un fichier .h et .c, c’est-à-dire les fichiers:

• bubble_sort.h, bubble_sort.c
• merge_sort.h, merge_sort.c
• radix_sort.h, radix_sort.c
• selection_sort.h, selection_sort.c
• quick_sort.h, quick_sort.c

qui contiennent la déclaration et l’implémentation des fonctions de tri à proprement parler (bubble_sort(), selection_sort(), etc.).

Il faut également créer:

• Les fichiers utils.h, utils.c qui contiennent les fonctions utilitaires telles que le calcul du minimum, l’échange de valeurs, l’affichage du tableau, la vérification que le tableau est trié, l’initialisation du tableau, etc (find_min(), swap(), print_tab(), is_sorted(), init(), …).
• Le fichier sorting_algorithms.c qui va contenir le point d’entrée de votre programme (la fonction main()) et qui aura pour tâche de faire une mesure de complexité de chaque tri en mesurant le temps CPU d’exécution de chaque tri. A cet effet, il vous faudra trier un tableau avec chaque tri et comparer les temps d’exécution en fonction de la taille des tableaux.

Votre projet devra se compiler à l’aide d’un Makefile. Ainsi, vous devez générer les cibles “objet”:

• bubble_sort.o,
• merge_sort.o,
• radix_sort.o,
• selection_sort.o,
• quick_sort.o,
• utils.o,
• sorting_algorithms.o,

et la cible “exécutable”:

• sorting_algorithms.

Pensez bien à mettre les dépendances correctes pour chaque cible, ainsi qu’une cible clean qui efface tous les produits de compilation (les .o et l’exécutable sorting_algorithms).

Remarque

1. Pour mesurer les temps d’exécution, utilisez des tableaux de taille 10_000, 20_000, 50_000, 100_000, 200_000, 500_000, 1000_000 et moyennez le temps d’exécution sur 100 répétitions de chaque tri. Reportez les résultats dans un tableau et affichez les graphes pour chaque tri à l’aide de l’outil d’affichage de votre choix (mais il est évidemment formellement interdit d’utiliser excel ou google sheet, car la librairie matplotlib de python fait parfaitement l’affaire). Vérifiez que les complexités sont bien celles vues en cours.
2. Pensez à bien ajouter l’option d’optimisation -O3 pour activer les options d’optimisation.
3. Vous serez tentés de faire un make clean && make pour compiler à chaque fois. Cela est aussi formellement interdit, car l’utilité du Makefile s’en trouve fortement réduite. En effet, le but d’un Makefile est d’éviter de recompiler des fichiers si aucune dépendance n’a changé.