Scribd
Importer
54 vues2 pages

Algorithmes de tri en C : Efficacité et tests

Ce document décrit les étapes pour implémenter et tester expérimentalement les algorithmes de tri par sélection et de tri fusion sur des tableaux générés aléatoirement. Il présente les fonctions à écrire pour générer les données, trier, chronométrer et afficher les résultats.

Transféré par

Karim Benyoussef
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOC, PDF, TXT ou lisez en ligne sur Scribd
54 vues2 pages

Algorithmes de tri en C : Efficacité et tests

Ce document décrit les étapes pour implémenter et tester expérimentalement les algorithmes de tri par sélection et de tri fusion sur des tableaux générés aléatoirement. Il présente les fonctions à écrire pour générer les données, trier, chronométrer et afficher les résultats.

Transféré par

Karim Benyoussef
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOC, PDF, TXT ou lisez en ligne sur Scribd

Ecole Hassania des Travaux Publics 1 ère Année, GC

M.K. GUENNOUN

TP3 Langage C
Efficacité expérimentale des algorithmes de tri

1. Ecrire un programme C dont la fonction main permet de générer aléatoirement les


éléments d’un tableau. Le programme :
a. demande dans un premier temps la taille du tableau
b. réserve la zone mémoire correspondant à cette taille (fonction malloc)
c. Il génèrera de manière aléatoire les éléments du tableau
i. Utiliser les fonctions srand et rand de la bibliothèque stdlib
1. Initialiser le générateur aléatoire par l’instruction :
srand(time(NULL))
2. Pour générer un entier aléatoirement, utiliser l’instruction
rand()
2. Ecrire une fonction afficher qui prend en paramètre ce tableau ainsi que sa taille pour
afficher son contenu
a. Signature : void afficher(int * tab, int taille)
3. Tester le programme en générant un tableau avec une taille saisie par l’utilisateur et
en affichant son contenu
4. Ecrire une fonction triParSelection qui prend en paramètre un tableau d’entiers ainsi
que sa taille et retourne un tableau de la même taille avec ses éléments triés du plus
petit au plus grand
a. Signature : int * Tri_Selection(int * tab, int taille)
5. Tester le programme en générant un tableau puis en l’affichant avant tri puis en
affichant le tableau résultant de l’appel de la fonction triParSelection
6. On souhaite actuellement comptabiliser le temps nécessaire pour effectuer le tri.
Nous allons pour cela utiliser la fonction clock() de la librairie time.h. Placer un appel
avant et après l’appel à la fonction triParSelection et puis afficher le temps calculé.
a. La fonction clock renvoie le temps CPU en millisecondes.
b. Utiliser le type double pour plus de précision
7. Introduire maintenant les fonctions relatives au tri par fusion. La fonction Tri_Fusion
prend en paramètre le tableau à trier ainsi que sa taille et renvoie un tableau
contenant les éléments de ce tableau dans l’ordre croissant.
a. void Fusionner(int * tab, int p, int q, int r)
b. void Tri_fusionPartiel(int * tab, int p, int r)
c. int * Tri_Fusion(int * tab, int taille)
8. En séquence de l’appel à la fonction Tri_Selection, introduire un appel à la fonction
Tri_Fusion.
a. Vérifier que les deux algorithmes renvoient le même résultat (utiliser des
tableaux de petites tailles)
b. Afficher les temps d’exécution pour les deux algorithmes. Utiliser des tailles
assez grandes (de l’ordre de 100 000) et conclure.

Vous aimerez peut-être aussi