Comparaison des tris

Sujet

L'objectif de ce TP est d'écrire un programme C qui compare les 4 tris de base : le tri par insertion, le tri par sélection (ou tri par minimum successif), le tri rapide et le tri par fusion. Voici un exemple d'exécution de ce programme :

$ bin/benchTri 
Nb d'entiers :50000
Test des tris sur 50000 entiers :
Tri Par Minimum Successif : 3.284840s (temps CPU)
Tri Par Insertion : 1.297865s (temps CPU)
Tri Rapide : 0.006665s (temps CPU)
Tri Par Fusion : 0.010241s (temps CPU)

Ce programme suivra les étapes suivantes :

  • Remplir un tableau avec n entiers (n saisi par l'utilisateur) aléatoires. n et le contenu du tableau seront de type long int.
  • Pour chaque tri :
    • Copier la zone mémoire dans une zone temporaire
    • Lancer le tri sur cette zone temporaire
    • Afficher le temps mis pour effecteur le tri (fonction clock de la bibliothèque time.h)

Ce programme sera composé des fichiers suivants :

  • src/main.c : le programme principal
  • include/echanger.h et src/echanger.c : les fonctions permettant d'échanger deux variables de même type (entre autres pour le type int, pour le type long int, etc.)
  • include/triParMinSuccessif.h et src/triParMinSuccessif.c
  • include/triParInsertion.h et src/triParInsertion.c
  • include/triRapide.h et src/triRapide.c
  • include/triFusion.h et src/triFusion.c
  • lib/libechanger.a : la bibliothèque statique qui contient echanger.o
  • lib/libtris.a : la bibliothèque statique qui contient triParMinimumSuccessof.o, triParInsertion.o, triRapide.o et triFusion.o
  • makefile, tel que :
    • make créera le programme bin/benchTri
    • make tests créera le programme de test unitaire tests/testTris

Consignes

Suivez les étapes suivantes:

  • Étape 1:
    • Créer l'arborescence (lib, bin, src, include, doc, tests)
    • Télécharger dans le répertoire src le fichier main (à renommer en main.c)
    • Créer les .h et les .c (fonctions sans corps pour les .c) bien faire attention au nom des fichiers, des fonctions et des paramètres formels (cf. le main.c)
    • Créer le programme de tests unitaires (en vous inspirant de celui du TP précédent) qui testera vos 4 algorithmes
    • Créer le makefile (vous n'êtes pas obligés d'utiliser les inférences et les variables internes)
    • Compiler et exécuter le projet 
  • Étape 2:
    • Développer la fonction benchmarkerUnTri de main.c
    • Compiler et  exécuter le projet 
  • Étape 3:
    • Développer le tri par minimum successif
    • Compiler et exécuter le projet
  • Étape 4:
    • Développer le tri par insertion
    • Compiler et exécuter le projet 
  • Étape 5:
    • Développer le tri rapide
    • Compiler et exécuter le projet
  • Étape 6:
    • Développer le tri par fusion
    • Compiler et exécuter le projet
  • Étape 7:
    • Tester le benchmark avec 10000, 20000, 50000 et 100000 éléments
    • Modifier le main  remplir au hasard de façon à trier un tableau déjà trié. Refaire le benchmark
Modifié le: mercredi 11 octobre 2017, 07:47