:: Enseignements :: ESIPE :: E3INFO :: 2013-2014 :: Algorithmique ::

Tris (suite)

Les TP 4 et 5 donneront lieu à un rapport qui sera à déposer sur la plateforme Moodle après la prochaine séance de TP. Ce rapport contiendra les explications des algorithmes, et des tests que vous avez choisis, la complexité de vos algorithmes et les diagrammes. Vous comparerez différents algorithmes de tris. Toutes vos réponses doivent être bien motivées.

Exercice 1 - Tri fusion

Écrire les fonctions permettant le tri d'un tableau d'entiers par tri fusion. N'oubliez pas d'utiliser vos tests de la séance précédente.

Exercice 2 - Tri rapide

Écrire les fonctions permettant le tri d'un tableau d'entiers par tri rapide.

Exercice 3 - Comparaisons

En utilisant gnuplot, visualiser le nombre de comparaisons et de déplacements pour le tri fusion et le tri rapide. Comparer avec les autres tris.
Combien d'entiers pouvez-vous trier en 10 secondes avec les différents algorithmes de tri ? En 20 secondes ?
Pour mesurer, vous pouvez utiliser time ./prog dans le terminal pour lancer le programme prog et afficher le temps de son exécution.
Pour des très grands tableaux, la pile d'exécution n'est pas suffisamment grande et vous obtenez une Segmentation fault. Pour résoudre ce problème vous pouvez allouer les tableaux sur le tas avec malloc.
Répondre à la même question en utilisant des tableaux décroissants, [taille-1, taille-2, ..., 2, 1, 0], au lieu de tableaux aléatoires. Expliquer le comportement du tri rapide.

Exercice 4 - Tri rapide dans <stdlib.h>

La librairie standard (<stdlib.h>) du C contient une fonction de tri appelée qsort. Vous trouvez un exemple de son utilisation ici.

Pour voir le code d'une implémentation de la libc, vous pouvez regarder ici : The GNU C Library. Naviger vers le code de la fonction qsort. Quelles améliorations sont implantées pour le tri rapide ?